创想实验室
我们都是梦想家

神奇的题目

描述

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.

输入

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.

输出

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.

样例输入

1

1

样例输出

1

样例输入

5

5 1 2 3 4

样例输出

5

题解

给一串1~n的排序(a[1]~a[n]),让你删除一个数,使满足条件的数列b中元素最多。仅当a[i]是a[1]~a[i]中最大的一个时,它才能被写入b序列。

因为是否符合条件要符合从前到自己中,自己是最大的,且只删除一个。那么只需维护已知序列一个最大值和一个次大值即可(最大到次大这个范围内的数是当前最大值能影响的范围)。通过和1~i-1中的最大值比较可以判断第i个数有没有符合条件的可能性。当第i个数大于之前的最大值时,当前数变为最大值,a[i]要被删去的可能性降低;当第i个数大于之前次大值小于最大值时,最大值要被删去的可能性上升。最后遍历这个权值(类似可能性)数组就可以了

 

网站所发布的代码已提交通过,代码可能经过修改防止抄袭,未经允许不得转载:创想实验室 » 神奇的题目
分享到: 更多 (0)

评论 2

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
  1. #1

    dalao牛逼

    taoting11个月前 (12-14)回复
    • 假象

      ArcherLuo11个月前 (12-14)回复