[Round#424 Div2] E. Cards Sorting

http://codeforces.com/contest/831/problem/E

E. Cards Sorting

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

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.

---

카드가 순서대로 쌓여있을 때, 가장 앞에있는 카드를 뽑아 현재 있는 카드들 중 가장 작은숫자를 뽑았는지 확인한다.

만약 뽑은 카드가 가장 작은 숫자가 아닐경우, 뽑은 카드를 가장 뒤로 보내고 가장 작은 숫자가 나올때 까지 반복해서 뽑는다.

반대로 뽑은 카드가 가장 작은 숫자일 경우 그 카드는 버리고, 남아있는 카드 중 가장 작은 숫자가 나올 때 까지 다시 뽑는다.

이렇게 카드 뽑기를 반복했을 때, 모든 카드를 버리게 될 때 까지 카드를 총 몇 번 뽑아야 하는지를 묻는 문제이다.

카드에 같은값이 없다면, 인덱스트리 하나만 가지고 쉽게 해결할 수 있다.

하지만 카드에 같은값이 중복되어 있기 때문에, 

마지막으로 뽑은 카드 위치부터 우리가 다음에 뽑아야 할 카드의 위치 사이에 카드가 몇개 있는지를 나타내는 sum indexed tree(tree[])와 다음 뽑아야 할 카드의 위치를 나타내주는 min indexed tree(tree2[]) 를 가지고 문제를 해결할 수 있다.

개인적으론 앞에 포스팅했던 C번문제는 한시간가까이 고민하면서 풀고, E번문제는 10분안에 해결했던 듯....

순서대로 풀지않는 습관을 들여야 하는데 참 쉽지않다

#include <stdio.h>
#include <algorithm>
#include <vector>
#define MAXN 100004
#define ll long long

using namespace std;

__inline pair<int, int> min(pair <int, int> a, pair<int, int> b) {
	return a < b ? a : b;
}
int n, sz, C[MAXN], low, mid, hi, idx, idx2, pre, now, p, pp;
int tree[262150];
pair<int, int> tree2[262150];
int main() {
	scanf("%d", &n);
	for (sz = 1; sz < n; sz <<= 1);
	sz--;
	for (int i = 1; i <= n; i++) scanf("%d", C + i);
	for (int i = 1; i <= n; i++) tree2[i+sz] = { C[i],i };
	for (int i = sz + n + 1; i <= sz * 2 + 1; i++) tree2[i] = { MAXN,MAXN };
	for (int i = sz; i; i--) tree2[i] = min(tree2[i * 2], tree2[i * 2 + 1]);
	sort(C + 1, C + n + 1);
	for (int i = 1; i <= n; i++) tree[sz + i] = 1;
	for (int i = sz; i; i--) tree[i] = tree[i * 2] + tree[i * 2 + 1];
	idx = 1;
	ll ans = 0;
	for (int i = 1; i <= n; i++) {
		low = sz + idx;
		hi = sz + n;
		pair <int, int> cand = { MAXN,MAXN };
		while (low <= hi) {
			if (low & 1) cand = min(cand, tree2[low]);
			if (!(hi & 1)) cand = min(cand, tree2[hi]);
			low = (low + 1) >> 1;
			hi = (hi - 1) >> 1;
		}
		if (cand.first == C[i]) {
			low = sz + idx;
			hi = sz+cand.second;
			while (low <= hi) {
				if (low & 1) ans += tree[low];
				if (!(hi & 1)) ans += tree[hi];
				low = (low + 1) >> 1;
				hi = (hi - 1) >> 1;
			}
			idx2 = sz + cand.second;
			while (idx2) {
				tree[idx2]--;
				idx2 >>= 1;
			}
			idx2 = sz + cand.second;
			tree2[idx2] = { MAXN,MAXN };
			idx2 >>= 1;
			while (idx2) {
				if (tree2[idx2] != cand) break;
				tree2[idx2] = min(tree2[idx2*2],tree2[idx2*2+1]);
				idx2 >>= 1;
			}
			idx = cand.second + 1;
		}
		else {
			low = sz + idx;
			hi = sz + n;
			while (low <= hi) {
				if (low & 1) ans += tree[low];
				if (!(hi & 1)) ans += tree[hi];
				low = (low + 1) >> 1;
				hi = (hi - 1) >> 1;
			}
			idx = 1;
			i--;
		}
	}
	printf("%lld", ans);
}