Problem Description

Marton’s friend Cero has an array of $N$ positive integers.

First, Cero writes the first number of this array on the blackboard. Then, each time he writes the next number either to the left or to the right of all the numbers already written. Repeating this operation produces a sequence.

Note that two sequences constructed in this way are considered the same if and only if the writing order and the side chosen for every number are exactly the same. For example, $1,1$ may be different from $1,1$: in the former, the second number is written to the left of the first one, while in the latter, the second number is written to the right of the first one.

Among all sequences that can be formed, let $M$ be the maximum possible length of the longest strictly increasing subsequence. Also, among all sequences whose longest strictly increasing subsequence length equals $M$, compute the sum of the numbers of longest strictly increasing subsequences. Since the answer may be very large, output this value modulo $10^9+7$.

Input Format

The first line contains a positive integer $N$.

The next line contains $N$ positive integers, the elements of the array given in order.

Output Format

Output one line containing the maximum length $M$ and the required total count modulo $10^9+7$.

2
1 1 

1 4 

4
2 1 3 4 

4 1

Hint

Sample Explanation

Sample 1 Explanation

Cero can construct $2$ different sequences: $1,1$ and $1,1$.

Clearly, the length of the longest strictly increasing subsequence is $1$, and there are $4$ subsequences that satisfy this.

Sample 2 Explanation

The length of the longest strictly increasing subsequence is $4$, and only $1,2,3,4$ satisfies this.

Constraints

For $30\%$ of the testdata, $N \le 20$.

For $50\%$ of the testdata, $N \le 10^3$.

For $100\%$ of the testdata, $N \le 2 \times 10^5$, and each element in the array is $\le 10^9$.

Note

Translated from COCI2016-2017 CONTEST #3 T5 Zoltan.

The explanations for Samples 1 and 2 are unofficial.

Translated by ChatGPT 5