U Akaki es una baraja de n cartas. Cada tarjeta tiene exactamente un número entero del 1 al 100 000 escrito en ella. Es posible que los mismos números estén escritos en algunas tarjetas.
Akaki decidió clasificar todas las cartas de la baraja. Para hacer esto, toma una carta superior de la baraja y si el número escrito en ella es igual al mínimo entre todos los números restantes en la baraja, deja esta carta a un lado. De lo contrario, Akaki pone esta carta en la parte inferior de la baraja y toma la siguiente carta de la parte superior de la baraja. El proceso termina cuando no quedan cartas en el mazo. Podemos suponer que Akaki en cualquier momento conoce el número mínimo escrito en algunas de las cartas restantes del mazo, pero no sabe dónde se encuentra esta carta (o cartas) en el mazo.
Tu tarea es determinar el número total de veces que Akaki mira la carta superior del mazo.
Entrada
La primera línea va seguida de un número entero positivo n (1 ≤ n ≤ 100 000) — el número de cartas en la baraja.
La segunda línea contiene una secuencia de n enteros positivos a
1, a
2, ..., a
n ( 1 ≤ a
i ≤ 100 000), donde a
i es igual al número escrito en la i-ésima carta superior desde el mazo.< /div>
Salida
Imprime el número total de veces que Akaki mira la carta superior de la baraja.
|
Entrar |
Salida |
|
4
6 3 1 2
|
7 |
1
1000
|
1 |
7
3 3 3 3 3 3 3
|
7 |
Nota
En el primer ejemplo, Akaki mirará primero la carta con el número 6, la colocará en la parte inferior de la baraja, luego la carta con el número 3, también la colocará en la parte inferior de la baraja, y luego la carta con el número 1. Dejará a un lado la carta con el número 1, ya que contiene el número mínimo para que quede en la baraja. Después de eso, las cartas de la baraja estarán en el orden [2, 6, 3] de arriba a abajo. Después de eso, Akaki mirará la carta superior con el número 2 y la dejará a un lado. Después de eso, las cartas de la baraja estarán en el orden [6, 3] de arriba a abajo. Entonces Akaki mirará la carta con el número 6, la pondrá en el fondo de la baraja, y luego la carta con el número 3, que apartará. Después de eso, quedará una carta con el número 6 en la baraja, que Akaki mirará y apartará. Por lo tanto, Akaki mirará 7 cartas.
(c) E. Kurbatov, 2018