题目背景

IOI2009 D1T1

题目描述

一场箭术比赛正在举行。一条直线上排着 $N$ 个靶子，靶子从左到右依次标号为从 $1$ 到 $N$。有 $2N$ 个选手，在比赛的任何时刻，同一个靶位上都有两个选手。比赛的每一轮按照如下规则进行：

• 在同一个靶位的两位选手比赛一场决出胜者，然后所有选手按照如下规则移动：

  • 在 $2$ 到 $N$ 号靶位上的胜者移动到他们的左侧的靶位（即分别移动到 $1\sim N - 1$ 号靶位）。
  • 在 $2$ 到 $N$ 号靶位上的负者，以及 $1$ 号靶位上的胜者，停留在同一个靶位。
  • $1$ 号靶位上的负者移动到 $N$ 号靶位。

比赛一共持续 $R$ 轮，轮数至少为参赛选手的数量，即 $R\geq 2N$。

你是唯一一个准时到达的选手。其它 $2N - 1$ 个选手已经提前到达并站成了一排，你现在要做的就是插入这个队伍。在你进入队伍后，队列中前两个选手（最左侧的两个选手）将对应一号靶位，接下来两个选手将对应二号靶位，以此类推，最右侧的两个选手对应 $N$ 号靶位。

所有 $2N$ 个选手（包括你）都用一个数值衡量技术水平，没有两个选手的技术水平相同。在同一个靶位上，数值较小的选手会成为胜者。

在了解了所有选手的技术水平之后，你需要找到一个位置插入使得你最终对应的靶位序号尽量小，在此前提下，你希望你初始时对应的靶位序号尽量大。

任务：编写一个程序，给定所有选手的技术水平（包括你自己）和你的对手们的排列顺序，计算出你的初始靶位编号，以满足你的上述目标。

输入格式

第一行包含两个由空格隔开的整数 $N, R$，分别表示靶位数和比赛轮数。

接下来 $2N$ 行给出选手的排列 $S_1, S_2, \cdots, S_{2N}$。$S_1$ 表示你的排名，$S_2, S_3, \cdots, S_{2N}$ 表示其他选手的排名，依照他们已经排列好的顺序（由左至右）。$S_k$ 是 $1\sim 2N$ 的整数，排名 $1$ 表示最好，排名 $2N$ 表示最差。没有两位选手的排名相同。

输出格式

输出一个 $1\sim N$ 的整数，表示开始的箭靶编号。

4 8
7
4
2
6
5
8
1
3

3

4 9
2
1
5
8
3
4
7
6

2

提示

样例解释

• 样例 1：你是排名倒数第二的选手。如果你从靶 $1$ 开始比赛，接下来你将移动到靶 $4$ 而且一直留在靶 $4$ 直到最后。如果你从靶 $2$ 或靶 $4$ 开始，你将会一直留到最后。如果你从靶 $3$ 开始，你将会击败最差的选手，然后移到靶 $2$ 并留在那里。

• 样例 2：你是排名第二的选手。排名第一的选手在靶 $1$ 并一直留在那里。因此，无论你从哪里出发，你永远会按 $4\to 3\to 2\to 1\to 4$ 的顺序循环移动。为了最终留在靶 $1$，你应该从靶 $2$ 开始。

数据范围与约定

• 对于 $20\%$ 的数据，$N\leq 200$。
• 对于 $60\%$ 的数据，$N\leq 5000$。
• 对于 $100\%$ 的数据，$1\leq N\leq 2\times 10 ^ 5$，$2N\leq R\leq 10 ^ 9$，$1\leq S_k\leq 2N$ 且 $S_k$ 互不相同。

另有三组