CF#484 Div2 D. Shark
? 解题记录 ? ? Codeforces ? ? 并查集 ?    2018-07-10 17:52:07    420    0    0

For long time scientists study the behavior of sharks. Sharks, as many other species, alternate short movements in a certain location and long movements between locations.

Max is a young biologist. For nn days he watched a specific shark, and now he knows the distance the shark traveled in each of the days. All the distances are distinct. Max wants to know now how many locations the shark visited. He assumed there is such an integer kk that if the shark in some day traveled the distance strictly less than kk, then it didn't change the location; otherwise, if in one day the shark traveled the distance greater than or equal to kk; then it was changing a location in that day. Note that it is possible that the shark changed a location for several consecutive days, in each of them the shark traveled the distance at least kk.

The shark never returned to the same location after it has moved from it. Thus, in the sequence of nn days we can find consecutive nonempty segments when the shark traveled the distance less than kk in each of the days: each such segment corresponds to one location. Max wants to choose such kk that the lengths of all such segments are equal.

Find such integer kk, that the number of locations is as large as possible. If there are several such kk, print the smallest one.

Input

The first line contains a single integer nn (1n1051≤n≤105) — the number of days.

The second line contains nn distinct positive integers a1,a2,,ana1,a2,…,an (1ai1091≤ai≤109) — the distance traveled in each of the day.

Output

Print a single integer kk, such that

1. the shark was in each location the same number of days,
2. the number of locations is maximum possible satisfying the first condition,
3. kk is smallest possible satisfying the first and second conditions.
Examples
input
Copy
81 2 7 3 4 8 5 6
output
Copy
7
input
Copy
625 1 2 3 14 36
output
Copy
2
Note

In the first example the shark travels inside a location on days 11 and 22 (first location), then on 44-th and 55-th days (second location), then on 77-th and 88-th days (third location). There are three locations in total.

In the second example the shark only moves inside a location on the 22-nd day, so there is only one location.

## 我们考虑将答案k从1枚举到n，并且快速维护当前答案。这道题相当于是说将大于k的作为障碍，那么我们在答案+1的时候只需要考虑统计新出现的"障碍"造成的影响就可以了。这个地方我们直接把每个格子当成一个结点，用并查集维护连通性就可以了。

#include<cstdio>
#include<algorithm>
#define For(i, a, b) for(register int i = a; i <= b; ++i)
using namespace std;
const int maxn = 2e5 + 5;
typedef pair<int, int > pii;

namespace DSU {
int fa[maxn], siz[maxn];
void init(int n) {For(i, 1, n) fa[i] = i, siz[i] = 1;}
int find(int x) {return fa[x] == x ? x : fa[x] = find(fa[x]);}
void combine(int a, int b) {
siz[find(b)] += siz[find(a)];
fa[find(a)] = find(b);
}
}

int tot[maxn], num[maxn], n, u, v, now, nsize, flag, blk, ans;
pii a[maxn];

void Com(int a, int b) {
using namespace DSU;
int fda, fdb;
if(--tot[siz[fda = find(a)]] == 0) --flag;
if(--tot[siz[fdb = find(b)]] == 0) --flag;
combine(a, b);
if(tot[siz[find(b)]]++ == 0) ++flag;
}

void Ins(int a) {
if(tot[1]++ == 0) ++flag;
if(num[a - 1]) Com(a, a - 1), --nsize;
if(num[a + 1]) Com(a, a + 1), --nsize;
num[a] = 1;
}

int main() {
scanf("%d", &n), DSU::init(n);
For(i, 1, n) scanf("%d", &u), a[i] = make_pair(u, i);
sort(a + 1, a + n + 1), flag = 0;
For(i, 1, n) {
now = a[i].first;
while(a[i].first == a[i + 1].first)
++nsize, Ins(a[i].second), ++i;
++nsize, Ins(a[i].second);
if(flag == 1 && nsize > blk)
ans = now, blk = nsize;
}
printf("%d", ans + 1);
return 0;
}

420 人读过

0 条评论