3470. Zoltan

输入格式

The first line of input contains the integer $N$ ($1\le N\le 2\cdot {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$.

• In test cases worth 30% of total points, it will hold $N\le 20$.
• In test cases worth 50% of total points, it will hold $N\le 1000$.

输出格式

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.

2
1 1

1 4

4
2 1 3 4

4 1

提示

Clarification of the first example:
The longest strictly increasing subsequence that can be obtained is of length 1 and there are 4 of them. The first possible construction: writes down the first 1, the second 1 to the right: the obtained sequence is 1,1; there are two strictly increasing subsequences of length 1: 1 1 and 1 1. The second possible construction: writes down the first 1, the second 1 to the left: the obtained sequence is 1, 1; there are two strictly increasing subsequences of length 1: 1 1 i 1 1.

Clarification of the second example:
The longest strictly increasing subsequence that can be obtained is of length 4.
It can be obtained only if he constructs the sequence 1 2 3 4. In that construction, it is the only strictly increasing subsequence of length 4, so the number of such is 1.