[ioi2009]Archery

时间限制:10s      空间限制:128MB

题目描述

一场箭术比赛规则如下所示。在一条直线上排着N个靶子,靶子从左到右序号依次为从1到N。同时有2N个选手,在比赛的任何时刻,同一个靶位上都有两个选手。比赛的每一轮按照如下规则进行:
在同一个靶位的两位选手比赛一场决出胜者,然后所有选手按照如下规则移动:
在2到N号靶位上的胜者移动到他们的左侧的靶位(即分别移动到1到N-1号靶位)
在2到N号靶位上的负者,以及1号靶位上的胜者,停留在同一个靶位。
1号靶位上的负者移动到N号靶位。
这场比赛持续R轮(R>=2N)。
你作为唯一一个准时到达的选手(其他选手已经提前到达了并且排成了一行),你现在要做的就是插入这个队伍,在你进入队伍后,队列中前两个选手将对应一号靶位,接下来两个将对应二号靶位,以此类推。
所有的选手(包括你)都用一个数值衡量技术水平,在同一个靶位上,数值比较小的选手会成为胜者,没有两个选手的技术水平相同。
在了解了所有选手的技术水平之后,你需要找到一个位置插入使得你最终对应的靶位序号尽量小,在此前提下,你希望你初始时对应的靶位序号尽量大。
数据规模
1<=N<=200000
2*N<=R<=1000000000


输入格式


输出格式


样例输入

4 8
7
4
2
6
5
8
1
3

样例输出

3

提示

没有写明提示


题目来源

没有写明来源

Menuappsclose