Vudú


Submit solution


Points: 100 (partial)
Time limit: 4.0s
Java 8 6.0s
Python 12.0s
Memory limit: 256M

Author:
Problem types
Allowed languages
Ada, Assembly, Awk, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Lua, Pascal, Perl, Prolog, Python, Scala, Swift, VB

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 N días, donde el precio de muñecas a_i representa el precio de una muñeca hace i 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 P dado, ¿cuántos subarreglos consecutivos diferentes en los últimos N días hay, tal el precio promedio de un muñeco fue mayor o igual a P? ".

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 N, la longitud de la secuencia (1 \leq N \leq 1 000 000). La segunda línea de insumo contiene N precios a_i (0 \leq a_i \leq 1 000 000 000) . La tercera línea de entrada contiene un número entero P. (0 \leq P \leq 1 000 000 000).

Salida

La primera y única línea de salida debe contener la respuesta a la pregunta de Mirko para un P 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 3 es \{3\}.

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 2 son \{1, 3\}, \{1, 3, 2\}, \{3\}, \{3, 2\}, \{2\}.

Ejemplo de entrada 3
3
1 3 2
3
Ejemplo de salida 3
1

Comments

There are no comments at the moment.