瓦西里有一副由n张牌组成的牌。每张卡片上都有一个整数,该整数在 1 到 100 000 之间(含 1 和 100 000)。有些卡上可能有相同的整数。
瓦西里决定对卡片进行排序。为此,他反复从牌堆中取出最上面的牌,如果牌上的数字等于牌堆中牌上写的最小数字,那么他就把牌放在一边。否则,他将其放在牌堆下面并从顶部取出下一张牌,依此类推。一旦牌组中没有牌,该过程就会结束。你可以假设瓦西里总是知道剩余牌中某张牌上写的最小数字,但不知道这张牌(或这些牌)在哪里。
你要确定瓦西里从牌堆中取出顶牌的总次数。
输入
第一行包含单个整数 n (1 ≤ n ≤ 100 000) — 这副牌中的牌数。
第二行包含 n 个整数 a1, a2, ..., an (1 ≤ ai ≤ 100 000) 的序列,其中 ai 是写在这副牌中从顶牌开始的第 i 张牌上的数字。
输出
打印瓦西里从牌堆中取出顶牌的总次数。
示例
输入 #1
4 6 3 1 2
输出 #1
7
输入 #2
1 1000
输出 #2
1
输入 #3
7 3 3 3 3 3 3 3
输出 #3
7
注意
在第一个例子中,瓦西里首先查看了数字6的牌,将其放在牌堆下,然后查看了数字3的牌,将其放在牌堆下,然后查看了数字1的牌。他将数字1的牌收了起来,因为上面写的数字是剩余牌中最小的。之后从上到下的牌是[2,6,3]。然后瓦西里查看最上面的数字 2 的卡片并将其收起来。之后从上到下的牌是[6, 3]。然后瓦西里看了看牌 6,把它放在牌堆下面,然后看牌 3,把它收起来。然后只剩下一张牌,上面写着数字6,瓦西里看了看,然后收了起来。因此,瓦西里总共看了 7 张牌。