题目描述

给定正整数序列 $ x_1 \sim x_n $，以下递增子序列均为非严格递增。

1. 计算其最长递增子序列的长度 $ s $。
2. 计算从给定的序列中最多可取出多少个长度为 $ s $ 的递增子序列。
3. 如果允许在取出的序列中多次使用 $ x_1 $ 和 $ x_n $，则从给定序列中最多可取出多少个长度为 $ s $ 的递增子序列。

输入格式

文件第 $ 1 $ 行有 $ 1 $ 个正整数 $ n $，表示给定序列的长度。接下来的 $ 1 $ 行有 $ n $ 个正整数 $ x_1 \sim x_n $。

输出格式

第 $ 1 $ 行是最长递增子序列的长度 $ s $。第 $ 2 $ 行是可取出的长度为 $ s $ 的递增子序列个数。第 $ 3 $ 行是允许在取出的序列中多次使用 $ x_1 $ 和 $ x_n $ 时可取出的长度为 $ s $ 的递增子序列个数。

样例

input

4
3 6 2 5

output

2
2
3

数据范围与提示

$ 1 \leq n \leq 500 $