Longest Increasing Subsequence 6

Time limit2sMemory limit512 MB

Summary

For a sequence of up to one million integers, report the length of the longest strictly increasing subsequence and the number of such subsequences modulo 1e9+7.

Level: Medium7 of 10
Topics: Dynamic programming, Binary search, Sorting, Segment tree
Solved: No attempts yet

Problem

Given a sequence A, write a program that finds the length and the number of the longest increasing subsequences.

For example, for the sequence A = {10, 20, 10, 30, 20, 50}, the longest increasing subsequence is A = {10, 20, 10, 30, 20, 50}, whose length is 4, and there is 1 of them. For A = {10, 20, 30, 10, 20, 30}, the longest increasing subsequence has length 3, and there are 4 of them.

Input

The first line gives the size N of the sequence A (1 ≤ N ≤ 1,000,000).

The second line gives Ai, the elements of the sequence A. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000)

Output

On the first line, print the length and the number of the longest increasing subsequences of the sequence A. Because the number can grow very large, print it modulo 109+7.

Examples3

Example 1
Input
```
6
10 20 10 30 20 50
```
Expected output
```
4 1
```
Example 2
Input
```
6
10 20 30 10 20 30
```
Expected output
```
3 4
```
Example 3
Input
```
10
3 2 1 6 5 4 10 9 8 7
```
Expected output
```
3 36
```