Pares Encantadores

View as PDF

Submit solution

Points: 100 (partial)
Time limit: 5.0s
Memory limit: 512M

Author:
Problem type

El ogro Ork tiene un arreglo \(A = [a_{1}, a_{2}, \dots, a_{n}]\) compuesto por \(n(1 \le n \le 5*10^5)\) números enteros en el rango \(1 \dots 10^9\). Él sabe que si un par \((a_{i}, a_{j})\) de elementos cumplen que \(a_{i} * a_{j} <= max (a_{i}, a_{i+1}, \dots, a_{j})\) este par es encantador. Ayude a Ork a contar el número de pares \((a_{i}, a_{j})\) con \(i < j\) que son encantadores.

Entrada

La primera línea contiene un número entero \(n\), la cantidad de elementos del arreglo.

La segunda línea contiene \(n\) números enteros, los elementos del arreglo.

Salida

La primera y única línea de salida contine un número entero, la cantidad de pares \((a_{i}, a_{j})\) con \(i < j\) que son encantadores.

Ejemplo de Entrada

5  
1 1 2 4 2

Ejemplo de Salida

8

Explicación del Ejemplo

Los pares encantadores son: \((1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5)\) y \((3, 5)\). Por lo que se imprime \(8\) como respuesta.


Comments

There are no comments at the moment.