Codeforces Round #443 (Div. 2) B. Table Tennis（模拟）-蒲公英云

Codeforces Round #443 (Div. 2) B. Table Tennis（模拟）

B. Table Tennis

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

n people are standing in a line to play table tennis. At first, the first two players in the line play a game. Then the loser goes to the end of the line, and the winner plays with the next person from the line, and so on. They play until someone wins k games in a row. This player becomes the winner.

For each of the participants, you know the power to play table tennis, and for all players these values are different. In a game the player with greater power always wins. Determine who will be the winner.

Input

The first line contains two integers: n and k (2 ≤ n ≤ 500, 2 ≤ k ≤ 1012) — the number of people and the number of wins after which a player leaves, respectively.

The second line contains n integers a1, a2, …, a**n (1 ≤ a**i ≤ n) — powers of the player. It’s guaranteed that this line contains a valid permutation, i.e. all a**i are distinct.

Output

Output a single integer — power of the winner.

Examples

input

2 2
1 2

output

input

4 2
3 1 2 4

output

input

6 2
6 5 3 1 2 4

output

input

2 10000000000
2 1

output

Note

Games in the second sample:

3 plays with 1. 3 wins. 1 goes to the end of the line.

3 plays with 2. 3 wins. He wins twice in a row. He becomes the winner.

题解：

本来也是很水的一题，昨天大意了早早得锁掉了题emmmm然后被人hack了，后来发现hack我的那个人自己那题也被别人hack了hhhhhhhhh

后来发现是手抖打错一个地方qaq，样例莫名其妙就过了

就是当k>=n时就直接输出最大的那个，否则用队列模拟（因为n最大才500）

代码:

#include<iostream>
#include<cstring>
#include<stdio.h>
#include<math.h>
#include<string>
#include<stdio.h>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#include<deque>
#include<algorithm>
#define ll long long
#define INF 1008611111
#define M (t[k].l+t[k].r)/2
#define lson k*2
#define rson k*2+1
using namespace std;
struct node
{
    int v;
    int p;
}a[505];
int cmp(node x,node y)
{
    return x.v>y.v;
}
queue<node>q;
int main()
{
    int i,j,n,k;
    int b[505];
    scanf("%d%d",&n,&k);
    for(i=1;i<=n;i++)
    {
        scanf("%d",&a[i].v);
        b[i]=a[i].v;
        a[i].p=i;
    }
    sort(a+1,a+n+1,cmp);
    if(k>=n-1)
    {
        printf("%d\n",a[1].v);
        return 0;
    }
    int add=0,d=1,tag=0;
    node now,next;
    while(1)
    {   if(!tag)
        for(i=2;i<=n;i++)
        {
            if(b[d]>b[i])
            {
                add++;
                if(add>=k)
                {
                    printf("%d\n",b[d]);
                    return 0;
                }
                now.p=i;
                now.v=b[i];
                q.push(now);
            }
            else
            {
                now.p=d;
                now.v=b[d];
                q.push(now);
                add=1;
                d=i;
            }
        }
        else
        {
            while(!q.empty())
            {
                now=q.front();
                q.pop();
                if(now.v>b[d])
                {
                    next.p=d;
                    next.v=b[d];
                    add=1;
                    q.push(next);
                    d=now.p;
                }
                else
                {
                    add++;
                    if(add>=k)
                    {
                        printf("%d\n",b[d]);
                        return 0;
                    }
                    q.push(now);
                }
            }
        }
        tag=1;
    }
    return 0;
}