A1347 | [COCI-2016_2017-contest3]#6 Zoltan

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.

The first line of input contains the integer N (1 ≤ N ≤ 2 * 10^5 ).
The following line contains N space-separated 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.