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