시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 0 0 0 0.000%

문제

재현이는 얼마 전 토너먼트 형태의 양궁 대회를 열었다. 1번부터 N번까지 번호가 매겨진 N개의 표적이 일직선상에 순서대로 (가장 좌측에 1번부터 시작하여 오른쪽에 N번으로 끝난다.) 나열되어 있으며, 2*N 명의 궁수들이 있다.

토너먼트는 다음과 같이 진행된다 - 한 표적에는 항상 2명의 궁수들이 할당되어 있으며, 두 궁수는 한 표적을 두고 경쟁하며 승자와 패자를 가른다. 승자와 패자가 결정된 후에는, 2 ~ N 표적에서 승리한 궁수들이 왼쪽 표적으로 이동하며 (1 ~ N-1 표적으로), 2 ~ N 표적에서 패배한 궁수들은 그 자리에 머무른다. 이 때 1번 표적에서 승리한 궁수는 그 자리에 머무르며, 1번 표적에서 패배한 궁수는 N번째 표적으로 이동한다. 이 토너먼트는 R번 진행되며, R >= 2*N임이 보장된다.

경험있는 양궁 해설가 승원이는 자신을 포함에서 이번에 출전하는 양궁 선수의 실력 등급을 모두 알고 있다. 각 선수의 실력 등급은 1 ~ 2*N 까지의 수로 표시되며, 등급이 낮은 선수일수록 뛰어난 선수이다. 승원이의 이 데이터는 정말 정확해서, 항상 실력이 높은 선수가 실력이 낮은 선수를 이긴다는 사실을 보장할 수 있다. 승원이는 양궁 해설에 타고난 재능을 가지고 있지만 이상하게 양궁 자체에는 별 관심이 없어서, 이번 대회에서 이기는 것보다는 오늘 밤 있는 코드포스 라운드를 놓치지 않는 것에 더 관심이 있다. 출구는 맨 왼쪽에 있기 때문에, 승원이는 R번의 라운드가 끝나고 나서 가장 왼쪽 타겟에 서 있기를 원한다.

다행이도, 승원이를 제외한 2*N-1명의 궁수가 연습을 위해 일찍 대회장에 나와있었다. 승원이는 적절한 위치에 끼어들어가서 양궁 경기를 시작하려 한다. 과연 승원이는 어떠한 위치에 끼어들어가야지 가장 일찍 집에 들어갈 수 있을까?

입력

표준 입력으로부터 다음의 데이터를 읽어야 한다 :

  • 첫번째 줄에 N과 R이 주어진다.
  • 두번째 줄에는 승원이의 실력 등급이 주어진다.
  • 세번째 줄 이후 2*N-1개의 줄에 각 선수의 실력 등급이 주어진다. 현재 선수들은 주어지는 순서대로 왼쪽에서 오른쪽으로 서 있다. 즉 세번째 줄에 적혀있는 선수가 가장 왼쪽에 있으며, 2*N+1번째 줄에 적혀있는 선수가 가장 오른쪽에 있다. 실력 등급은 2*N 보다 작거나 같은 서로 다른 자연수ㅇ다.
  • 1 <= N <= 200000
  • 2*N <= R <= 1,000,000,000

출력

승원이가 집에 일찍 들어가기 위해 끼어들어가야 할 위치를 출력한다. 이 때 위치는, 승원이가 처음 경쟁할 때 삼을 표적의 번호를 뜻한다. 만약에 최적의 위치가 여러 곳이라면, 그 중 가장 번호가 높은 위치를 출력하면 된다.

예제 입력

4 8
7
4
2
6
5
8
1
3

예제 출력

3

예제 입력 2

4 9
2
1
5
8
3
4
7
6

예제 출력 2

2

힌트

승원이의 실력 등급은 7이다. 1번 표적에서 시작할 경우 승원이는 4번 표적으로 간 후 끝까지 해당 표적에 머무른다. 2번 표적이나 4번 표적에서 시작할 경우 승원이는 끝까지 해당 표적에 머무른다. 3번 표적에서 시작할 경우 승원이는 실력 등급이 8인 궁수를 이기고 2번 표적에 끝까지 머무른다.

출처

Olympiad > International Olympiad in Informatics > IOI 2009 1번

  • 문제를 번역한 사람: koosaga