Excellent Team（模拟，细节）

A - Excellent Team

Time Limit:1000MS Memory Limit:65536KB 64bit IO Format:%I64d & %I64u

Submit Status Practice URAL 1931

Description

Gibbs: Next!
First Pirate: My wife ran off with my dog and I'm drunk for a month.
Gibbs: Perfect. Next!
Second Pirate: Me have one arm and a bum leg.
Gibbs: It's the crow's nest for you. Next!

In Tortuga the Captain Jack Sparrow and Will Turner set up an excellent team. And now Jack wants to elect a captain's mate — the most worthy pirate in the new crew, who has fewer disadvantages and can be a role model for the rest.

Without thinking a lot Jack decided to use the following uncomplicated plan to choose the best pirate of the crew. Firstly, he ranks ncontenders in one long row, beckons the first one and this first pirate is a current contender to be the mate. Then Jack walks along the row and stares at everybody one by one. He compares the regular pirate with the current contender and if he sees that the regular pirate has fewer disadvantages, then he changes the current contendor to the regular pirate. In the end of this process the new mate will stand near Jack.

Will knows about Jack’s plan and wants to count what pirate will have most comparisons while Jack elects. Let’s help Will with his calculations.

Input

The first line contains an integer n that is the number of pirates in the crew (1 ≤ n ≤ 10⁵). Next line contains n integers: a₁, a₂, …, a_n, wherea_i is the number of disadvantages of i-th contender in Jack's opinion (1 ≤ a_i ≤ 10⁹). The pirates are numbered in the way they stood in the row in the beginning of the elections. It is guaranteed that the numbers of disadvantages, which the pirates have, are pairwise different.

Output

Output the number of a pirate who was compared with others maximal number of times. If there are several such pirates, you can output any of them.

Sample Input

input	output
6 2 5 3 4 1 9	1

原题连接：http://acm.hust.edu.cn:8080/judge/contest/view.action?cid=17352#problem/A

这题不难，但是很容易就WA……

关键点：当更换contendor时，新的contendor已经经历了一次比较。

AC Code：

 1 #include <iostream>
 2 #include <string>
 3 #include <cstdio>
 4 #include <cmath>
 5 #include <cstring>
 6 #include <algorithm>
 7 #include <map>
 8 #include <vector>
 9 #include <queue>
10 #include <stack>
11 #define LL long long
12 #define MAXI 2147483647
13 #define MAXL 9223372036854775807
14 #define eps (1e-8)
15 #define dg(i) cout << "*" << i << endl;
16 
17 using namespace std;
18 
19 int a[100001];
20 
21 int main()
22 {
23     int n, m, cnt, maxCnt, ans, j;
24     while (scanf("%d", &n) != EOF)
25     {
26         j = 0;
27         cnt = 0;
28         maxCnt = -1;
29         ans = 0;
30         scanf("%d", &a[0]);
31         for (int i = 1; i < n; ++i)
32         {//cout << "j = " << j << endl;
33             scanf("%d", &a[i]);
34             if (a[j] < a[i])
35             {
36                 cnt++;  //比较次数+1
37             }
38             else
39             {
40                 cnt++;
41                 if (cnt > maxCnt)
42                 {
43                     maxCnt = cnt;
44                     ans = j;
45                 }
46                 j = i;
47                 cnt = 1;  //不能恢复cnt为0！！！因为替换contendor时已比较一次
48             }
49         }
50         if(cnt > maxCnt) ans = j;
51         printf ("%d\n", ans + 1);
52     }
53     return 0;
54 }