Cero el amigo de Marton tiene un arreglo de ~N~ enteros. Al comienzo, Cero escribe el primer número en el tablero. Luego él escribe el segundo número a la izquierda o a la derecha del primer número. Después de eso, él escribe el tercer número a la izquierda o a la derecha de los números escritos hasta el momento, y así sucesivamente. Marlon le preguntó a Cero cuál era es la longitud de la subsecuencia posible estrictamente creciente (no necesariamente de elementos posibles).

El también quiere saber el número de tales subsecuencias más largas estrictamente crecientes. Más precisamente, si la longitud de la subsecuencia más larga estrictamente creciente es ~M~, él quiere saber la suma de números de subsecuencias estrictamente crecientes de longitud ~M~ para cada posible secuencia que Cero pueda construir. Las secuencias son diferentes si están construidas usando ordenes diferentes de movimientos, y la subsecuencias en una secuencia construida son diferentes si difieren al menos en una posición.

Dado que el número de tales subsecuencias puede ser extremadamente largo, Marlon quedará satisfecho con el valor de ese número módulo ~10^9+7~.

Cero realmente no tiene tiempo en el momento para encontrar las respuestas a las preguntas de Mrton, por lo tanto, él le está pidiendo a usted que lo ayude.

Entrada

La primera línea de la entrada contiene el entero ~N (1 \leq N \leq 2 * 10^5)~. La siguiente línea contiene N enteros separados por espacios representando los elementos en el arreglo de Cero. Cada número en la entrada será menor o igual que ~10^9~.

Salida

Usted debe dar como salida una sola línea, la longitud de la subsecuencia más larga estrictamente creciete y el número de subsecuencias estrictamente crecientes de esa longitud, módulo ~10^9+7~.

Ejemplo #1 de Entrada

2
1 1

Ejemplo #1 de Salida

1 4

Ejemplo #2 de Entrada

4
2 1 3 4

Ejemplo #2 de Salida

4 1

Aclaración del primer caso de prueba: La subsecuencia estrictamente creciente más larga que puede ser obtenida es de longitud 1 ya hay 4 de ellas. La primera construcción posible escribe el primer 1, el segundo 1 a la derecha y la secuencia obtenida es 1,1: hay dos subsecuencias estrictamente crecientes de longitud 1: 11 y 1 1. La segunda construcción posible escribe el primer 1, el segundo 1 a la izquierda, la secuencia obtenida es 1,1: hay dos subsecuencias estrictamente crecientes de longitud 1: 11 y 1 1.

Aclaración del segundo caso de prueba: La subsecuencia estrictamente creciente más grande que puede ser obtenida es de longitud 4. Puede ser obtenida únicamente si se construye la secuencia 1 2 3 4. Esa construcción es la única subsecuencia estrictamente creciente de longitud 4, entonces el número de tales subsecuencias es 1