Vudú
El joven Mirko ha estado comprando muñecos vudú últimamente. Teniendo en cuenta que está muy interesado en lo más barato posible, ha estado rastreando los precios de los muñecos vudú todos los días. Su lista de precios consta de precios de muñecas en los últimos días, donde el precio de muñecas representa el precio de una muñeca hace días.
Mirko cree que ha notado una conexión entre el precio promedio de un muñeco en una secuencia de días y el precio al día siguiente. Quiere poner a prueba su corazonada y está desconcertado por una muy interesante pregunta: "Para un dado, ¿cuántos subarreglos consecutivos diferentes en los últimos días hay, tal el precio promedio de un muñeco fue mayor o igual a ? ".
Dos subarreglos consecutivos se consideran diferentes si sus comienzos o finales son diferentes.
Entrada
La primera línea de entrada contiene el número entero , la longitud de la secuencia . La segunda línea de insumo contiene precios . La tercera línea de entrada contiene un número entero . .
Salida
La primera y única línea de salida debe contener la respuesta a la pregunta de Mirko para un determinado.
Puntuación
En los casos de prueba que valgan el 30% de los puntos, la longitud de la secuencia N será menor o igual a 10 000.
Ejemplos
Ejemplo de entrada 1
3
1 2 3
3
Ejemplo de salida 1
1
Aclaración del primer ejemplo: El único subarreglo que tiene un promedio mayor o igual a es .
Ejemplo de entrada 2
3
1 3 2
2
Ejemplo de salida 2
5
Aclaración del segundo ejemplo: Los subarreglos que tienen un promedio mayor o igual a son , , , , .
Ejemplo de entrada 3
3
1 3 2
3
Ejemplo de salida 3
1
Comments