1 \(s / 32\) \(MB / 140\) points

Marton’s friend Cero has an array of \(N\) positive integers. In the beginning, Cero writes the

first number on the board. Then he writes the second number to the left or to the right of the

first number. After that, he writes the third number to the left or to the right of all the numbers

written so far, and so on.

Marton asked Cero what the length of the longest possible strictly increasing subsequence

(not necessarily of consecutive elements) was.

He also wants to know the number of such longest strictly increasing subsequences. More

precisely, if the length of the longest increasing subsequence is \(M\)

, he wants to know the

sum of numbers of strictly increasing subsequences of length \(M\) for each possible sequence

that Cero can construct. The sequences are different if they are constructed using a different

order of moves, and the subsequences in a constructed sequence are different if they differ

in at least one position.

Given the fact that the number of such subsequences can be extremely large, Marton will be

satisfied with the value of that number modulo 10 ^{9}{ } + 7.

Cero really doesn’t have time at the moment to find out the answers to Marton’s questions,

so he is asking you to do it for him.

In test cases worth 30% of total points, it will hold \(N\)

≤ 20.
In test cases worth 50% of total points, it will hold \(N\)

≤ 1000.

The first line of input contains the integer \(N\)

(1 ≤ \(N\)

≤ \(2 * 10\) ^{5}{ }).
The following line contains \(N\)

spa\(ce-se\)parated integers that represent the elements of Cera’s
array. Each number in the input will be smaller than or equal to 10 ^{9}{ }.

You must output, in 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,

respectively.

생성자가 기록되지 않았습니다.

출처 COCI 2016/2017 Contest 3