[Round#450 Div2] C. Remove Extra One

http://codeforces.com/problemset/problem/900/C

C. Remove Extra One

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given a permutation p of length n. Remove one element from permutation to make the number of records the maximum possible.

We remind that in a sequence of numbers a1, a2, ..., ak the element ai is a record if for every integer j (1 ≤ j < i) the following holds: aj < ai.

Input

The first line contains the only integer n (1 ≤ n ≤ 105) — the length of the permutation.

The second line contains n integers p1, p2, ..., pn (1 ≤ pi ≤ n) — the permutation. All the integers are distinct.

Output

Print the only integer — the element that should be removed to make the number of records the maximum possible. If there are multiple such elements, print the smallest one.

Examples

input

1
1

output

1

input

5
5 1 2 3 4

output

5

Note

In the first example the only element can be removed.

---

주어져 있는 수열 {p1, p2, ..., pn} 에서 어떤 pk를 제거했을때 나머지 각 pi 들에 대해  pj < pi. (1 ≤ j < i)를 만족하는 pi(record)를 최대로 가지게 할 수 있는가를 문제다.

pk 를 제거했을때  record의 개수에 영향을 미치는 경우는

먼저 pk 자신이 기존에 record인 경우 자신을 제외시키기 때문에 총 records 수가 하나 감소 하게 된다.

기존엔 record가 아니었으나 pk를 제거했을때 record가 되는 pi 의 조건을 생각해보면

1. pk보다 오른쪽에 위치해야 하며

2. pi보다 왼쪽에 있는 수열 중 pk를 제외한 나머지 수들은 모두 pi보다 작아야만 pk를 제거했을 때 record가 된다.

따라서 왼쪽에서부터 순차적으로 indexed tree에 넣으면서 현재 자신의 값(pi)보다 큰 값이 기존에 몇개 있었는지 개수를 세면서 탐색해 나가면 된다. 단, 같은 cost를 가지는 수열들에 대해선 가장 작은 값을 출력하라는 부분만 조심해서 작성하면 된다. 시간복잡도는 O(NlgN)

개인적으로 오랜만에 문제 풀다보니 간단한데도 엄청 버벅버벅..

#include <stdio.h>

#define MAXN (int)1e5+7
int tree[262145],idx_tree[262145], arr[MAXN], n, sz, left, right, idx,d[MAXN], ans;
int main(){
	scanf("%d", &n);
	for (sz = 1; sz <= n; sz <<= 1);
	sz--;
	for (int i = 1; i <= n; i++)scanf("%d", arr + i);
	for (int i = 1; i <= n; i++){
		left = sz + arr[i] + 1;
		right = sz + n;
		int val = 0;
		while (left <= right && val<2){
			if ((left & 1) && tree[left]) {
				val += tree[left];
				idx = idx_tree[left];
			}
			if (!(right & 1) && tree[right]) {
				val += tree[right];
				idx = idx_tree[right];
			}
			left = (left + 1) >> 1;
			right = (right - 1) >> 1;
		}
		if (val == 0) d[arr[i]]--;
		else if (val == 1)d[idx]++;
		idx = sz + arr[i];
		while (idx){
			tree[idx] ++;
			idx_tree[idx] = arr[i];
			idx >>= 1;
		}
	}
	ans = -2;
	for (int i = 1; i <= n; i++){
		if (ans < d[i]){
			ans = d[i];
			idx = i;
		}
	}
	printf("%d", idx); 

}