Zoltan | cho.sh

Problem

Marton's friend Cero has an array of $N$ positive integers. Cero first writes the first number of the array on the board. He then writes the second number either to the left or to the right of the first one. The third number goes to the left or to the right of everything written so far, and the remaining numbers follow the same way, in array order.

Marton asked Cero how long the longest strictly increasing subsequence of such a sequence can be. The elements of a subsequence do not have to be consecutive.

Marton also wants to know how many such subsequences there are. Let $M$ be the length of the longest strictly increasing subsequence over every sequence Cero can build. For each sequence Cero can build, count the strictly increasing subsequences of length $M$ , then report the sum of those counts. Two sequences are different if the left or right choice differs at least once, and two subsequences of one sequence are different if they differ in at least one position.

The count can be very large, so give it modulo $10^9 + 7$ .

Cero has no time to work out the answers right now, so he is asking you to do it for him.

Input

The first line contains the integer $N$ $(1 \le N \le 2 \times 10^5)$ .

The second line contains the $N$ elements of Cero's array, separated by spaces. Each element is a positive integer not greater than $10^9$ .

Output

Print, on a single line, the length of the longest strictly increasing subsequence and the number of strictly increasing subsequences of that length modulo $10^9 + 7$ , separated by a space.

Hint

Take $N = 2$ with the array $1, 1$ . The longest strictly increasing subsequence has length 1, and there are 4 of them in total.

In the first construction Cero writes the first 1 and then puts the second 1 to the right. The sequence is $1, 1$ , and it has two strictly increasing subsequences of length 1: the first element alone and the second element alone.

In the second construction he puts the second 1 to the left. The sequence is again $1, 1$ and has the same two subsequences. Adding both constructions gives 4.