831_E. Cards Sorting_28692
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

4
6 3 1 2


Output

7


Input

1
1000


Output

1


Input

7
3 3 3 3 3 3 3


Output

7

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.
#include <bits/stdc++.h>
using namespace std;
struct BIT {
  int A[100007];
  void init() { fill_n(A, 100007, 0); }
  void add(int i, int k) {
    for (; i < 100007; i += (i) & (-i)) A[i] += k;
  }
  int get(int i) {
    int s = 0;
    for (; i > 0; i -= (i) & (-i)) s += A[i];
    return s;
  }
  int get(int l, int r) { return get(r) - get(l - 1); }
};
struct comp {
  bool operator()(pair<int, int> a, pair<int, int> b) {
    if (a.first != b.first) return a.first > b.first;
    return a.second > b.second;
  }
};
vector<int> Ko[100007];
int main() {
  ios_base::sync_with_stdio(0), cin.tie(NULL), cout.tie(NULL);
  int n;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    int c;
    cin >> c;
    Ko[c].push_back(i);
  }
  BIT X;
  X.init();
  for (int i = 1; i <= n; i++) X.add(i, 1);
  int st = 0;
  long long ans = 0;
  for (int c = 0; c <= 100000; c++) {
    int maxi = Ko[c].size();
    for (int i = 0; i < Ko[c].size(); i++) {
      if (Ko[c][i] >= st) {
        maxi = min(maxi, i);
        ans += X.get(st, Ko[c][i]);
        X.add(Ko[c][i], -1);
        st = Ko[c][i];
      }
    }
    for (int i = 0; i < maxi; i++) {
      if (Ko[c][i] >= st) {
        ans += X.get(st, Ko[c][i]);
        X.add(Ko[c][i], -1);
        st = Ko[c][i];
      } else {
        ans += X.get(st, n);
        ans += X.get(1, Ko[c][i]);
        X.add(Ko[c][i], -1);
        st = Ko[c][i];
      }
    }
  }
  cout << ans;
}

4
6 3 1 2
 1
1000
 7
3 3 3 3 3 3 3
 87
12 2 2 10 12 1 5 9 15 2 4 7 7 14 8 10 1 6 7 6 13 15 10 6 2 11 13 1 15 14 8 8 4 7 11 12 3 15 9 2 13 1 7 11 2 1 13 11 8 14 2 2 12 7 13 4 13 3 13 3 11 1 7 13 15 8 12 4 12 4 1 4 9 3 13 12 10 15 14 10 7 7 7 2 7 6 10
 20
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
 30
6283 14661 69188 39640 41261 48019 86266 70517 4592 69008 20602 33339 29980 96844 76008 96294 27120 22671 5243 742 33692 18068 29056 48033 1223 82728 99765 38350 36425 10671
 100
9 9 72 55 14 8 55 58 35 67 3 18 73 92 41 49 15 60 18 66 9 26 97 47 43 88 71 97 19 34 48 96 79 53 8 24 69 49 12 23 77 12 21 88 66 9 29 13 61 69 54 77 41 13 4 68 37 74 7 6 29 76 55 72 89 4 78 27 29 82 18 83 12 4 32 69 89 85 66 13 92 54 38 5 26 56 17 55 29 4 17 39 29 94 3 67 85 98 21 14
 64
826 142 89 337 897 891 1004 704 281 644 910 852 147 193 289 384 625 695 416 944 162 939 164 1047 359 114 499 99 713 300 268 316 256 404 852 496 373 322 716 202 689 857 936 806 556 153 137 863 1047 678 564 474 282 135 610 176 855 360 814 144 77 112 354 154
 10
4 3 4 3 3 3 4 4 4 3
 87
12 2 2 10 12 1 5 9 15 2 4 7 7 14 8 10 1 6 7 6 13 15 10 6 2 11 13 1 15 14 8 14 4 7 11 12 3 15 9 2 13 1 7 11 2 1 13 11 8 14 2 2 12 7 13 4 13 3 13 3 11 1 7 13 15 8 12 4 12 4 1 4 9 3 13 12 10 15 14 10 7 7 7 2 7 6 10
 30
6283 14661 69188 39640 41261 48019 86266 70517 1276 69008 20602 33339 29980 96844 76008 96294 27120 22671 5243 742 33692 18068 29056 48033 1223 82728 99765 38350 36425 10671
 100
9 9 72 55 14 8 55 58 35 67 3 18 73 92 41 49 15 60 18 66 9 26 97 47 43 88 71 97 19 34 48 96 79 53 8 24 69 49 12 23 77 12 21 88 66 9 29 13 61 69 54 77 41 13 4 68 37 74 7 6 29 76 55 72 89 4 78 27 29 82 18 83 12 4 32 69 89 85 66 13 92 54 38 5 26 6 17 55 29 4 17 39 29 94 3 67 85 98 21 14
 64
826 142 89 337 897 891 1004 704 281 644 910 852 147 193 289 384 625 695 416 944 162 939 164 1047 359 114 499 99 713 300 268 316 256 404 852 496 373 322 716 202 689 857 936 806 556 204 137 863 1047 678 564 474 282 135 610 176 855 360 814 144 77 112 354 154
 10
4 3 4 3 3 2 4 4 4 3
 4
6 2 1 2
 1
1001
 7
3 5 3 3 3 3 3
 87
12 2 2 10 12 1 6 9 15 2 4 7 7 14 8 10 1 6 7 6 13 15 10 6 2 11 13 1 15 14 8 14 4 7 11 12 3 15 9 2 13 1 7 11 2 1 13 11 8 14 2 2 12 7 13 4 13 3 13 3 11 1 7 13 15 8 12 4 12 4 1 4 9 3 13 12 10 15 14 10 7 7 7 2 7 6 10
 30
6283 14661 69188 39640 41261 48019 86266 66388 1276 69008 20602 33339 29980 96844 76008 96294 27120 22671 5243 742 33692 18068 29056 48033 1223 82728 99765 38350 36425 10671
 64
826 142 89 337 897 891 1004 704 281 644 910 852 147 19 289 384 625 695 416 944 162 939 164 1047 359 114 499 99 713 300 268 316 256 404 852 496 373 322 716 202 689 857 936 806 556 204 137 863 1047 678 564 474 282 135 610 176 855 360 814 144 77 112 354 154
 10
4 6 4 3 3 2 4 4 4 3
 4
6 2 2 2
 87
12 2 2 10 12 1 6 9 15 2 4 7 7 14 8 10 1 6 7 6 13 15 10 6 2 11 13 1 15 14 8 14 4 7 11 12 3 15 9 2 13 1 7 11 2 1 13 11 8 14 2 2 12 7 13 4 13 3 13 3 11 1 7 13 15 8 12 4 12 4 1 4 9 3 13 12 10 15 14 10 7 7 7 2 1 6 10
 30
6283 14661 69188 39640 41261 48019 86266 66388 1276 69008 20602 33339 29980 96844 76008 96294 27120 22671 5243 742 33692 24056 29056 48033 1223 82728 99765 38350 36425 10671
 64
826 142 89 337 897 891 1004 704 281 644 910 852 147 19 289 384 625 695 416 944 162 939 164 1047 359 114 499 99 713 300 268 316 256 404 852 496 72 322 716 202 689 857 936 806 556 204 137 863 1047 678 564 474 282 135 610 176 855 360 814 144 77 112 354 154
 10
4 6 4 3 3 2 6 4 4 3
 7
3 5 3 3 3 3 7
 87
12 2 2 10 12 1 6 9 15 2 4 7 7 14 8 10 1 6 7 6 13 15 10 6 2 11 13 1 15 14 8 14 4 7 11 12 3 15 9 2 13 1 7 11 2 1 13 11 8 14 2 2 12 7 13 4 13 3 13 3 11 1 7 13 15 8 12 4 12 4 1 4 9 3 13 12 10 15 14 10 7 7 7 2 1 4 10
 30
6283 14661 69188 39640 41261 48019 86266 66388 1276 69008 20602 33339 38772 96844 76008 96294 27120 22671 5243 742 33692 24056 29056 48033 1223 82728 99765 38350 36425 10671
 64
826 142 89 337 897 891 1004 704 281 644 910 852 147 19 289 384 625 695 416 944 162 939 164 1047 359 114 499 99 713 300 268 316 256 404 852 496 72 322 716 202 689 857 936 58 556 204 137 863 1047 678 564 474 282 135 610 176 855 360 814 144 77 112 354 154
 87
12 2 2 10 12 1 6 9 15 2 4 7 7 14 8 10 1 6 7 6 13 15 10 6 2 11 13 1 15 14 8 14 4 7 11 12 3 15 9 2 13 1 7 11 2 1 13 11 8 14 2 2 12 7 13 4 13 3 13 3 11 1 7 13 15 8 12 4 12 4 1 4 9 3 13 12 17 15 14 10 7 7 7 2 1 4 10
 64
826 142 89 337 897 891 1004 704 281 644 910 852 147 19 289 384 625 695 416 944 162 939 164 1047 359 114 499 99 713 300 268 316 256 404 852 496 72 322 716 202 689 857 936 58 556 204 137 863 1047 678 564 474 282 135 610 176 855 360 128 144 77 112 354 154
 87
12 2 2 10 12 1 6 9 15 2 4 7 7 14 8 10 1 6 7 6 4 15 10 6 2 11 13 1 15 14 8 14 4 7 11 12 3 15 9 2 13 1 7 11 2 1 13 11 8 14 2 2 12 7 13 4 13 3 13 3 11 1 7 13 15 8 12 4 12 4 1 4 9 3 13 12 17 15 14 10 7 7 7 2 1 4 10
 64
826 142 89 337 897 891 1004 704 281 644 910 852 147 19 318 384 625 695 416 944 162 939 164 1047 359 114 499 99 713 300 268 316 256 404 852 496 72 322 716 202 689 857 936 58 556 204 137 863 1047 678 564 474 282 135 610 176 855 360 128 144 77 112 354 154
 87
12 2 2 10 12 1 6 9 15 2 4 7 7 14 8 10 1 6 7 6 4 15 10 6 2 11 13 1 15 14 8 14 4 7 11 12 3 15 9 2 13 1 7 11 2 1 13 11 8 14 2 2 12 7 13 4 13 3 13 3 11 1 7 13 15 8 12 4 12 4 1 4 9 3 13 12 17 15 14 10 7 7 7 2 2 4 10
 10
2 6 8 3 3 2 8 4 1 3
 64
826 142 89 349 897 891 1004 704 281 644 910 852 147 19 318 384 625 695 416 944 162 939 164 1047 359 114 499 99 713 300 268 316 256 404 852 496 72 322 716 202 689 842 936 58 556 204 137 863 1047 678 564 474 282 135 610 176 855 360 128 144 77 112 354 154
 10
2 6 8 3 3 2 8 4 1 5
 64
826 142 89 349 897 891 1004 704 281 644 910 852 147 19 318 384 625 695 416 944 162 939 164 1047 359 114 403 99 713 300 268 316 256 404 852 496 72 322 716 202 689 842 936 58 556 204 137 863 1047 678 564 474 282 135 610 176 855 360 128 144 77 112 354 154
 64
826 142 89 349 897 891 1004 704 281 644 910 852 147 19 318 384 625 695 416 944 162 939 191 1047 359 114 403 99 713 300 268 316 256 404 852 496 72 322 716 202 689 842 936 58 556 204 137 863 1047 678 564 474 282 135 610 176 855 360 128 144 77 112 354 154
 10
2 6 8 3 3 1 8 4 1 5
 64
826 142 89 349 897 891 1004 704 281 644 910 852 147 19 318 384 625 695 416 944 162 939 191 1047 359 114 403 99 713 300 268 316 256 404 852 496 72 322 716 202 689 842 936 58 556 204 137 863 1047 678 564 474 282 135 610 176 855 360 128 144 77 200 354 154
 64
826 142 89 349 897 891 1004 704 281 644 910 852 147 19 318 384 625 695 416 944 162 939 191 1047 359 114 403 99 713 300 268 316 256 404 852 496 72 322 716 202 689 842 936 58 556 204 137 863 1047 678 364 474 282 135 610 176 855 360 128 144 77 200 354 154
 64
826 142 89 550 897 891 1004 704 281 644 910 852 147 19 318 384 625 695 416 944 162 939 191 1047 359 114 403 99 713 300 268 316 256 404 852 496 72 322 716 202 689 842 936 58 556 204 137 863 1047 678 364 474 282 135 610 176 855 360 128 144 77 200 354 154
 64
826 142 89 550 897 891 1004 704 281 644 1493 852 147 19 318 384 625 695 416 944 162 939 191 1047 359 114 403 99 713 300 268 316 256 404 852 496 72 322 716 202 689 842 936 58 556 204 137 863 1047 678 364 474 282 135 610 176 855 360 128 144 77 200 354 154
 100
9 9 72 55 14 8 55 58 35 67 3 18 73 92 41 49 15 60 18 66 9 26 97 47 43 88 71 97 19 34 48 96 79 52 8 24 69 49 12 23 77 12 21 88 66 9 29 13 61 69 54 77 41 13 4 68 37 74 7 6 29 76 55 72 89 4 78 27 29 82 18 83 12 4 32 69 89 85 66 13 92 54 38 5 26 6 17 55 29 4 17 39 29 94 3 67 85 98 21 14
 1
0001
 7
3 5 3 3 3 3 4
 4
6 4 2 2
 10
4 6 8 3 3 2 6 4 4 3
 4
6 4 4 2
 30
6283 14661 69188 39640 41261 48019 86266 66388 1276 69008 20602 33339 38772 96844 76008 96294 27120 22671 2006 742 33692 24056 29056 48033 1223 82728 99765 38350 36425 10671
 10
4 6 8 3 3 2 8 4 4 3
 4
6 2 4 2
 10
2 6 8 3 3 2 8 4 4 3
 4
6 2 4 4
 64
826 142 89 349 897 891 1004 704 281 644 910 852 147 19 318 384 625 695 416 944 162 939 164 1047 359 114 499 99 713 300 268 316 256 404 852 496 72 322 716 202 689 857 936 58 556 204 137 863 1047 678 564 474 282 135 610 176 855 360 128 144 77 112 354 154
 4
10 2 4 4
 4
10 1 4 4
 10
2 6 8 3 3 3 8 4 1 5
 10
2 5 8 3 3 1 8 4 1 5
 10
2 2 8 3 3 1 8 4 1 5
 10
2 2 8 3 3 1 8 4 1 4

7
 1
 7
 580
 20
 235
 1805
 1042
 15
 585 235 1786 1044 20 7 1 8 570 234 1037 22 5 574 212 989 23 9 573 210 1029 578 1064 571 1102 563 28 1114 29 1085 1086 21 1139 1168 1163 1167 1786 1 8 7 23 8 210 22 7 20 5 1102 5 5 22 21 20 20