Secuencia invisible


Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 64M

Author:
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. Una secuencia invisible en esta cadena es de la forma a_i, a_i + 1 ,..., a_j, donde i \le j.

Ejemplo

Para N = 4 y la cadena 2 3 4 3, las secuencias invisibles son: 2, 2 3, 2 3 4, 2 3 4 3, 3, 3 4, 3 4 3, 4, 4 3, 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, la potencia del elemento a_1 es 1 (siendo máxima solo en la secuencia formada por sí misma), del elemento a_2 siendo 2 (a_2 siendo máxima en las secuencias 2 3 y 3), del elemento a_3 siendo 6 (siendo máxima en secuencias 2 3 4, 2 3 4 3, 3 4, 3 4 3, 4 y 4 3), y del elemento a_4 es 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, y en la segunda línea, en orden, los números naturales 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
  • Los elementos de la cadena son números naturales y tienen un máximo de 6 dígitos.

Ejemplo #1 de Entrada

7
9 3 4 5 1 2 2

Ejemplo #1 de Salida

12
1

Explicación

El ítem 5 en la posición 4 es máximo en 12 secuencias: 3 4 5, 3 4 5 1, 3 4 5 1 2, 3 4 5 1 2 2, 4 5, 4 5 1, 4 5 1 2, 4 5 1 2 2, 5, 5 1, 5 1 2, 5 1 2 2, entonces su potencia es 12. Es el único elemento que tiene esta potencia, los otros elementos tienen potencia más bajas.

Ejemplo #2 de Entrada

6
1 0 7 7 2 6

Ejemplo #2 de Salida

3
2

Explicación

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


Comments

There are no comments at the moment.