Secuencia invisible

Points: 100 (partial)

Time limit: 1.0s

Memory limit: 64M

Author:

leocar

Problem type

Allowed languages

Ada, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Lua, Pascal, Prolog, Python, Swift, VB

Consideramos una cadena de números $a_1, a_2, ..., a_N$ $a_{1}, a_{2}, . . ., a_{N}$ . Una secuencia invisible en esta cadena es de la forma $a_i, a_i + 1 ,..., a_j$ $a_{i}, a_{i} + 1, . . ., a_{j}$ , donde $i \le j$ $i \leq j$ .

Ejemplo

Para $N = 4$ $N = 4$ y la cadena $2 3 4 3$ $2343$ , las secuencias invisibles son: $2, 2 3, 2 3 4, 2 3 4 3, 3, 3 4, 3 4 3, 4, 4 3, 3$ $2, 23, 234, 2343, 3, 34, 343, 4, 43, 3$ . Definimos la potencia de un elemento que tiene como número de secuencias que lo contienen y en el que tiene es estrictamente mayor que los otros elementos de cada una de esas secuencias. Así, en la fila $2 3 4 3$ $2343$ , la potencia del elemento $a_1$ $a_{1}$ es $1$ $1$ (siendo máxima solo en la secuencia formada por sí misma), del elemento $a_2$ $a_{2}$ siendo $2$ $2$ ( $a_2$ $a_{2}$ siendo máxima en las secuencias $2 3$ $23$ y $3$ $3$ ), del elemento $a_3$ $a_{3}$ siendo $6$ $6$ (siendo máxima en secuencias $2 3 4, 2 3 4 3, 3 4, 3 4 3, 4$ $234, 2343, 34, 343, 4$ y $4 3$ $43$ ), y del elemento $a_4$ $a_{4}$ es $1$ $1$ .

Tarea

Escriba un programa que determine la potencia más alta de un elemento en la cadena dada, así como el número de elementos en la cadena que tienen la potencia más alta.

Entrada

La entrada contiene en la primera línea el número natural $N$ $N$ , y en la segunda línea, en orden, los números naturales $a_1, a_2, ..., a_N$ $a_{1}, a_{2}, . . ., a_{N}$ separados por un espacio.

Salida

La salida contendrá en la primera línea un número natural que representa la potencia más alta de un elemento en la cadena dada y en la segunda línea contendrá un número natural que representa el número de elementos en la cadena que tienen la potencia más alta.

Restricciones y especificaciones:

$2 \le N \le 200000$ $2 \leq N \leq 200000$
Los elementos de la cadena son números naturales y tienen un máximo de $6$ $6$ dígitos.

Ejemplo #1 de Entrada

Copy

7
9 3 4 5 1 2 2

Ejemplo #1 de Salida

Copy

12
1

Explicación

El ítem $5$ $5$ en la posición $4$ $4$ es máximo en $12$ $12$ secuencias: $3 4 5$ $345$ , $3 4 5 1$ $3451$ , $3 4 5 1 2$ $34512$ , $3 4 5 1 2 2$ $345122$ , $4 5$ $45$ , $4 5 1$ $451$ , $4 5 1 2$ $4512$ , $4 5 1 2 2$ $45122$ , $5$ $5$ , $5 1$ $51$ , $5 1 2$ $512$ , $5 1 2 2$ $5122$ , entonces su potencia es $12$ $12$ . Es el único elemento que tiene esta potencia, los otros elementos tienen potencia más bajas.

Ejemplo #2 de Entrada

Copy

6
1 0 7 7 2 6

Ejemplo #2 de Salida

Copy

3
2

Explicación

Los elementos en las posiciones $3$ $3$ y $4$ $4$ son máximos en $3$ $3$ secuencias, por lo que su potencia es $3$ $3$ . Los otros elementos tienen poderes más bajos.

Comments

There are no comments at the moment.