У Василия есть колода, состоящая из n карт. На каждой карте написано ровно одно целое число от 1 до 100 000. Возможно, что на некоторых картах написаны одинаковые числа.
Василий решил отсортировать все карты в колоде. Для этого он по очереди берёт одну верхнюю карту из колоды и если число, написанное на ней, равно минимальному среди всех оставшихся чисел в колоде, он откладывает эту карту в сторону. В противном случае, Василий кладёт эту карту вниз колоды и берёт сверху колоды следующую карту. Процесс заканчивается, когда в колоде не останется карт. Можно считать, что Василий в любой момент времени знает минимальное число, записанное на какой-то из оставшихся в колоде картах, но не знает, где эта карта (или карты) находится в колоде.
Перед вами стоит задача определить суммарное количество раз, которое Василий посмотрит верхнюю карту из колоды.
Выходные данные
Выведите суммарное количество раз, которое Василий посмотрит верхнюю карту из колоды.
Примечание
В первом примере Василий посмотрит сначала карту с числом 6, положит ее вниз колоды, затем карту с числом 3, также положит ее вниз колоды, и затем карту с числом 1. Он отложит карту с числом 1, так как на ней написан минимальное число из оставшихся в колоде. После этого карты в колоде будут лежать в порядке [2, 6, 3] сверху вниз. После этого Василий посмотрит верхнюю карту с числом 2 и отложит её. После этого карты в колоде будут лежать в порядке [6, 3] сверху вниз. Затем Василий посмотрит карту с числом 6, положит ее вниз колоды, а затем карту с числом 3, которую отложит. После этого в колоде останется одна карта с числом 6, которую Василий посмотрит и отложит. Таким образом, Василий посмотрит 7 карт.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
6 3 1 2
|
7
|
|
2
|
1
1000
|
1
|
|
3
|
7
3 3 3 3 3 3 3
|
7
|