[set]Codeforces 830B-Cards Sorting

Vasily has a deck of cards consisting of n cards. There is an integer on each of the cards, this integer is between 1 and 100 000, inclusive. It is possible that some cards have the same integers on them.

Vasily decided to sort the cards. To do this, he repeatedly takes the top card from the deck, and if the number on it equals the minimum number written on the cards in the deck, then he places the card away. Otherwise, he puts it under the deck and takes the next card from the top, and so on. The process ends as soon as there are no cards in the deck. You can assume that Vasily always knows the minimum number written on some card in the remaining deck, but doesn't know where this card (or these cards) is.

You are to determine the total number of times Vasily takes the top card from the deck.

Input

The first line contains single integer n (1 ≤ n ≤ 100 000) — the number of cards in the deck.

The second line contains a sequence of n integers a1, a2, ..., an (1 ≤ ai ≤ 100 000), where ai is the number written on the i-th from top card in the deck.

Output

Print the total number of times Vasily takes the top card from the deck.

Examples

input

Copy

4
6 3 1 2

output

Copy

input

Copy

1
1000

output

Copy

input

Copy

7
3 3 3 3 3 3 3

output

Copy

Note

In the first example Vasily at first looks at the card with number 6 on it, puts it under the deck, then on the card with number 3, puts it under the deck, and then on the card with number 1. He places away the card with 1, because the number written on it is the minimum among the remaining cards. After that the cards from top to bottom are [2, 6, 3]. Then Vasily looks at the top card with number 2 and puts it away. After that the cards from top to bottom are [6, 3]. Then Vasily looks at card 6, puts it under the deck, then at card 3 and puts it away. Then there is only one card with number 6 on it, and Vasily looks at it and puts it away. Thus, in total Vasily looks at 7 cards.

题意:给你n个数，这些数可能重复，每次取出当前第一个数，如果这个数是这些数中的最小值，则扔掉，否则放到最后

思路:若取出的这个数是最小的，则这些数的总数要减1，否则要放到末尾，如果我们把这些数都取了一遍，会发现下一个取数的周期中原来的数相对位置是不变的，比如说123->231->312->123

若要取出一个数，则必须先把它前面的那些数取出来，若要取末尾那个数，则其前面那些数都要被取出，即取出了这些数的总个数
首先我们记录数对应的下标有哪些，每次要取出最小的那个，所以我们先排个序从最小的那个开始找
一开始总数是n，第一次必定会把当前所有的数都取一遍，所以设答案初始值为n，现在从第一位开始找，设mid=1
每次会找大于等于mid的下标,如果找不到，会返回end()地址（也就是说当前集合中不存在大于等于mid的那个数）
如果找不到了，比如说上一个mid=4，而这个元素总只有1的下标，说明我们已经找过一次当前的所以数了，要把总数加上重新从开头找
每次要删掉当前最小的那个，同时总数减一

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int amn=1e5+5;
 5 int a[amn];
 6 set<int> p[amn];
 7 set<int>::iterator k;
 8 int main(){
 9     int n;
10     cin>>n;
11     for(int i=1;i<=n;i++){
12         cin>>a[i];
13         p[a[i]].insert(i);   ///记录数对应的下标有哪些
14     }
15     sort(a+1,a+1+n);        ///每次要取出最小的那个，所以我们先排个序从最小的那个开始找
16     ll tot=n,mid=1,ans=n;   ///一开始总数是n，第一次必定会把当前所有的数都取一遍，所以设答案初始值为n，现在从第一位开始找，设mid=1
17     for(int i=1;i<=n;i++){
18         k=p[a[i]].lower_bound(mid); ///每次会找大于等于mid的下标,如果找不到，会返回end()地址（也就是说当前集合中不存在大于等于mid的那个数）
19         if(k==p[a[i]].end()){   ///如果找不到了，比如说上一个mid=4，而这个元素总只有1的下标，说明我们已经找过一次当前的所以数了，要把总数加上重新从开头找
20             ans+=tot;           ///我们找过了所有数一遍，所以加上数的总个数
21             mid=1;              ///重新从第一位开始找
22             k=p[a[i]].lower_bound(mid);
23         }
24         mid=*k;
25         p[a[i]].erase(k);       ///删掉当前最小的那个
26         tot--;                  ///同时总数减一
27     }
28     printf("%lld
",ans);
29 }
30 /***
31 给你n个数，这些数可能重复，每次取出当前第一个数，如果这个数是这些数中的最小值，则扔掉，否则放到最后
32 若取出的这个数是最小的，则这些数的总数要减1，否则要放到末尾，如果我们把这些数都取了一遍，会发现下一个取数的周期中原来的数相对位置是不变的，比如说123->231->312->123
33 若要取出一个数，则必须先把它前面的那些数取出来，若要取末尾那个数，则其前面那些数都要被取出，即取出了这些数的总个数
34 首先我们记录数对应的下标有哪些，每次要取出最小的那个，所以我们先排个序从最小的那个开始找
35 一开始总数是n，第一次必定会把当前所有的数都取一遍，所以设答案初始值为n，现在从第一位开始找，设mid=1
36 每次会找大于等于mid的下标,如果找不到，会返回end()地址（也就是说当前集合中不存在大于等于mid的那个数）
37 如果找不到了，比如说上一个mid=4，而这个元素总只有1的下标，说明我们已经找过一次当前的所以数了，要把总数加上重新从开头找
38 每次要删掉当前最小的那个，同时总数减一
39 ***/