시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 8 4 2 40.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

출력

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

예제 입력 1

4 8
7
4
2
6
5
8
1
3

예제 출력 1

3

예제 입력 2

4 9
2
1
5
8
3
4
7
6

예제 출력 2

2

힌트

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

W3sicHJvYmxlbV9pZCI6IjU0NjAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM1OTFcdWFkODEiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzdhY1x1ZDYwNFx1Yzc3NFx1YjI5NCBcdWM1YmNcdWI5YzggXHVjODA0IFx1ZDFhMFx1YjEwOFx1YmEzY1x1ZDJiOCBcdWQ2MTVcdWQwZGNcdWM3NTggXHVjNTkxXHVhZDgxIFx1YjMwMFx1ZDY4Y1x1Yjk3YyBcdWM1ZjRcdWM1YzhcdWIyZTQuIDFcdWJjODhcdWJkODBcdWQxMzAgTlx1YmM4OFx1YWU0Y1x1YzljMCBcdWJjODhcdWQ2MzhcdWFjMDAgXHViOWU0XHVhY2E4XHVjOWM0IE5cdWFjMWNcdWM3NTggXHVkNDVjXHVjODAxXHVjNzc0IFx1Yzc3Y1x1YzljMVx1YzEyMFx1YzBjMVx1YzVkMCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgKFx1YWMwMFx1YzdhNSBcdWM4OGNcdWNlMjFcdWM1ZDAgMVx1YmM4OFx1YmQ4MFx1ZDEzMCBcdWMyZGNcdWM3OTFcdWQ1NThcdWM1ZWMgXHVjNjI0XHViOTc4XHVjYWJkXHVjNWQwIE5cdWJjODhcdWM3M2NcdWI4NWMgXHViMDVkXHViMDljXHViMmU0LikgXHViMDk4XHVjNWY0XHViNDE4XHVjNWI0IFx1Yzc4OFx1YzczY1x1YmE3MCwgMipOIFx1YmE4NVx1Yzc1OCBcdWFkODFcdWMyMThcdWI0ZTRcdWM3NzQgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQxYTBcdWIxMDhcdWJhM2NcdWQyYjhcdWIyOTQgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc3NCBcdWM5YzRcdWQ1ODlcdWI0MWNcdWIyZTQgLSBcdWQ1NWMgXHVkNDVjXHVjODAxXHVjNWQwXHViMjk0IFx1ZDU2ZFx1YzBjMSAyXHViYTg1XHVjNzU4IFx1YWQ4MVx1YzIxOFx1YjRlNFx1Yzc3NCBcdWQ1NjBcdWIyZjlcdWI0MThcdWM1YjQgXHVjNzg4XHVjNzNjXHViYTcwLCBcdWI0NTAgXHVhZDgxXHVjMjE4XHViMjk0IFx1ZDU1YyBcdWQ0NWNcdWM4MDFcdWM3NDQgXHViNDUwXHVhY2UwIFx1YWNiZFx1YzdjMVx1ZDU1OFx1YmE3MCBcdWMyYjlcdWM3OTBcdWM2NDAgXHVkMzI4XHVjNzkwXHViOTdjIFx1YWMwMFx1Yjk3OFx1YjJlNC4gXHVjMmI5XHVjNzkwXHVjNjQwIFx1ZDMyOFx1Yzc5MFx1YWMwMCBcdWFjYjBcdWM4MTVcdWI0MWMgXHVkNmM0XHVjNWQwXHViMjk0LCAyIH4gTiBcdWQ0NWNcdWM4MDFcdWM1ZDBcdWMxMWMgXHVjMmI5XHViOWFjXHVkNTVjIFx1YWQ4MVx1YzIxOFx1YjRlNFx1Yzc3NCBcdWM2N2NcdWNhYmQgXHVkNDVjXHVjODAxXHVjNzNjXHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU1OFx1YmE3MCAoMSB+IE4tMSBcdWQ0NWNcdWM4MDFcdWM3M2NcdWI4NWMpLCAyIH4gTiBcdWQ0NWNcdWM4MDFcdWM1ZDBcdWMxMWMgXHVkMzI4XHViYzMwXHVkNTVjIFx1YWQ4MVx1YzIxOFx1YjRlNFx1Yzc0MCBcdWFkZjggXHVjNzkwXHViOWFjXHVjNWQwIFx1YmEzOFx1YmIzNFx1Yjk3OFx1YjJlNC4gXHVjNzc0IFx1YjU0YyAxXHViYzg4IFx1ZDQ1Y1x1YzgwMVx1YzVkMFx1YzExYyBcdWMyYjlcdWI5YWNcdWQ1NWMgXHVhZDgxXHVjMjE4XHViMjk0IFx1YWRmOCBcdWM3OTBcdWI5YWNcdWM1ZDAgXHViYTM4XHViYjM0XHViOTc0XHViYTcwLCAxXHViYzg4IFx1ZDQ1Y1x1YzgwMVx1YzVkMFx1YzExYyBcdWQzMjhcdWJjMzBcdWQ1NWMgXHVhZDgxXHVjMjE4XHViMjk0IE5cdWJjODhcdWM5ZjggXHVkNDVjXHVjODAxXHVjNzNjXHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU1Y1x1YjJlNC4gXHVjNzc0IFx1ZDFhMFx1YjEwOFx1YmEzY1x1ZDJiOFx1YjI5NCBSXHViYzg4IFx1YzljNFx1ZDU4OVx1YjQxOFx1YmE3MCwgUiAmZ3Q7PSAyKk5cdWM3ODRcdWM3NzQgXHViY2Y0XHVjN2E1XHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjYmRcdWQ1ZDhcdWM3ODhcdWIyOTQgXHVjNTkxXHVhZDgxIFx1ZDU3NFx1YzEyNFx1YWMwMCBcdWMyYjlcdWM2ZDBcdWM3NzRcdWIyOTQgXHVjNzkwXHVjMmUwXHVjNzQ0IFx1ZDNlY1x1ZDU2OFx1YzVkMFx1YzExYyBcdWM3NzRcdWJjODhcdWM1ZDAgXHVjZDljXHVjODA0XHVkNTU4XHViMjk0IFx1YzU5MVx1YWQ4MSBcdWMxMjBcdWMyMThcdWM3NTggXHVjMmU0XHViODI1IFx1YjRmMVx1YWUwOVx1Yzc0NCBcdWJhYThcdWI0NTAgXHVjNTRjXHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHVhYzAxIFx1YzEyMFx1YzIxOFx1Yzc1OCBcdWMyZTRcdWI4MjUgXHViNGYxXHVhZTA5XHVjNzQwIDEgfiAyKk4gXHVhZTRjXHVjOWMwXHVjNzU4IFx1YzIxOFx1Yjg1YyBcdWQ0NWNcdWMyZGNcdWI0MThcdWJhNzAsIFx1YjRmMVx1YWUwOVx1Yzc3NCBcdWIwYWVcdWM3NDAgXHVjMTIwXHVjMjE4XHVjNzdjXHVjMjE4XHViODVkIFx1YjZmMFx1YzViNFx1YjA5YyBcdWMxMjBcdWMyMThcdWM3NzRcdWIyZTQuIFx1YzJiOVx1YzZkMFx1Yzc3NFx1Yzc1OCBcdWM3NzQgXHViMzcwXHVjNzc0XHVkMTMwXHViMjk0IFx1YzgxNVx1YjlkMCBcdWM4MTVcdWQ2NTVcdWQ1NzRcdWMxMWMsIFx1ZDU2ZFx1YzBjMSBcdWMyZTRcdWI4MjVcdWM3NzQgXHViMTkyXHVjNzQwIFx1YzEyMFx1YzIxOFx1YWMwMCBcdWMyZTRcdWI4MjVcdWM3NzQgXHViMGFlXHVjNzQwIFx1YzEyMFx1YzIxOFx1Yjk3YyBcdWM3NzRcdWFlMzRcdWIyZTRcdWIyOTQgXHVjMGFjXHVjMmU0XHVjNzQ0IFx1YmNmNFx1YzdhNVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWMyYjlcdWM2ZDBcdWM3NzRcdWIyOTQgXHVjNTkxXHVhZDgxIFx1ZDU3NFx1YzEyNFx1YzVkMCBcdWQwYzBcdWFjZTBcdWIwOWMgXHVjN2FjXHViMmE1XHVjNzQ0IFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODhcdWM5YzBcdWI5Y2MgXHVjNzc0XHVjMGMxXHVkNTU4XHVhYzhjIFx1YzU5MVx1YWQ4MSBcdWM3OTBcdWNjYjRcdWM1ZDBcdWIyOTQgXHViY2M0IFx1YWQwMFx1YzJlY1x1Yzc3NCBcdWM1YzZcdWM1YjRcdWMxMWMsIFx1Yzc3NFx1YmM4OCBcdWIzMDBcdWQ2OGNcdWM1ZDBcdWMxMWMgXHVjNzc0XHVhZTMwXHViMjk0IFx1YWM4M1x1YmNmNFx1YjJlNFx1YjI5NCBcdWM2MjRcdWIyOTggXHViYzI0IFx1Yzc4OFx1YjI5NCBcdWNmNTRcdWI0ZGNcdWQzZWNcdWMyYTQgXHViNzdjXHVjNmI0XHViNGRjXHViOTdjIFx1YjE5M1x1Y2U1OFx1YzljMCBcdWM1NGFcdWIyOTQgXHVhYzgzXHVjNWQwIFx1YjM1NCBcdWFkMDBcdWMyZWNcdWM3NzQgXHVjNzg4XHViMmU0LiBcdWNkOWNcdWFkNmNcdWIyOTQgXHViOWU4IFx1YzY3Y1x1Y2FiZFx1YzVkMCBcdWM3ODhcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwLCBcdWMyYjlcdWM2ZDBcdWM3NzRcdWIyOTQgUlx1YmM4OFx1Yzc1OCBcdWI3N2NcdWM2YjRcdWI0ZGNcdWFjMDAgXHViMDVkXHViMDk4XHVhY2UwIFx1YjA5OFx1YzExYyBcdWFjMDBcdWM3YTUgXHVjNjdjXHVjYWJkIFx1ZDBjMFx1YWM5Zlx1YzVkMCBcdWMxMWMgXHVjNzg4XHVhZTMwXHViOTdjIFx1YzZkMFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMmU0XHVkNTg5XHVjNzc0XHViM2M0LCBcdWMyYjlcdWM2ZDBcdWM3NzRcdWI5N2MgXHVjODFjXHVjNjc4XHVkNTVjIDIqTi0xXHViYTg1XHVjNzU4IFx1YWQ4MVx1YzIxOFx1YWMwMCBcdWM1ZjBcdWMyYjVcdWM3NDQgXHVjNzA0XHVkNTc0IFx1Yzc3Y1x1Y2MwZCBcdWIzMDBcdWQ2OGNcdWM3YTVcdWM1ZDAgXHViMDk4XHVjNjQwXHVjNzg4XHVjNWM4XHViMmU0LiBcdWMyYjlcdWM2ZDBcdWM3NzRcdWIyOTQgXHVjODAxXHVjODA4XHVkNTVjIFx1YzcwNFx1Y2U1OFx1YzVkMCBcdWIwN2NcdWM1YjRcdWI0ZTRcdWM1YjRcdWFjMDBcdWMxMWMgXHVjNTkxXHVhZDgxIFx1YWNiZFx1YWUzMFx1Yjk3YyBcdWMyZGNcdWM3OTFcdWQ1NThcdWI4MjQgXHVkNTVjXHViMmU0LiBcdWFjZmNcdWM1ZjAgXHVjMmI5XHVjNmQwXHVjNzc0XHViMjk0IFx1YzViNFx1YjVhMFx1ZDU1YyBcdWM3MDRcdWNlNThcdWM1ZDAgXHViMDdjXHVjNWI0XHViNGU0XHVjNWI0XHVhYzAwXHVjNTdjXHVjOWMwIFx1YWMwMFx1YzdhNSBcdWM3N2NcdWNjMGQgXHVjOWQxXHVjNWQwIFx1YjRlNFx1YzViNFx1YWMwOCBcdWMyMTggXHVjNzg4XHVjNzQ0XHVhZTRjPzxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVkNDVjXHVjOTAwIFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1Y1x1YmQ4MFx1ZDEzMCBcdWIyZTRcdWM3NGNcdWM3NTggXHViMzcwXHVjNzc0XHVkMTMwXHViOTdjIFx1Yzc3ZFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQgOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlx1Y2NhYlx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDAgTlx1YWNmYyBSXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9saT5cclxuXHQ8bGk+XHViNDUwXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMyYjlcdWM2ZDBcdWM3NzRcdWM3NTggXHVjMmU0XHViODI1IFx1YjRmMVx1YWUwOVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YzEzOFx1YmM4OFx1YzlmOCBcdWM5MDQgXHVjNzc0XHVkNmM0IDIqTi0xXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCBcdWFjMDEgXHVjMTIwXHVjMjE4XHVjNzU4IFx1YzJlNFx1YjgyNSBcdWI0ZjFcdWFlMDlcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWQ2MDRcdWM3YWMgXHVjMTIwXHVjMjE4XHViNGU0XHVjNzQwIFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjNjdjXHVjYWJkXHVjNWQwXHVjMTFjIFx1YzYyNFx1Yjk3OFx1Y2FiZFx1YzczY1x1Yjg1YyBcdWMxMWMgXHVjNzg4XHViMmU0LiBcdWM5ODkgXHVjMTM4XHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM4MDFcdWQ2MDBcdWM3ODhcdWIyOTQgXHVjMTIwXHVjMjE4XHVhYzAwIFx1YWMwMFx1YzdhNSBcdWM2N2NcdWNhYmRcdWM1ZDAgXHVjNzg4XHVjNzNjXHViYTcwLCAyKk4rMVx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjODAxXHVkNjAwXHVjNzg4XHViMjk0IFx1YzEyMFx1YzIxOFx1YWMwMCBcdWFjMDBcdWM3YTUgXHVjNjI0XHViOTc4XHVjYWJkXHVjNWQwIFx1Yzc4OFx1YjJlNC4gXHVjMmU0XHViODI1IFx1YjRmMVx1YWUwOVx1Yzc0MCAyKk4gXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWM3NDAgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCBcdWM3OTBcdWM1ZjBcdWMyMThcdTMxNDdcdWIyZTQuPFwvbGk+XHJcblx0PGxpPjEgJmx0Oz0gTiAmbHQ7PSAyMDAwMDA8XC9saT5cclxuXHQ8bGk+MipOICZsdDs9IFIgJmx0Oz0gMSwwMDAsMDAwLDAwMDxcL2xpPlxyXG48XC91bD5cclxuIiwib3V0cHV0IjoiPHA+XHVjMmI5XHVjNmQwXHVjNzc0XHVhYzAwIFx1YzlkMVx1YzVkMCBcdWM3N2NcdWNjMGQgXHViNGU0XHVjNWI0XHVhYzAwXHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWIwN2NcdWM1YjRcdWI0ZTRcdWM1YjRcdWFjMDBcdWM1N2MgXHVkNTYwIFx1YzcwNFx1Y2U1OFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1Yzc3NCBcdWI1NGMgXHVjNzA0XHVjZTU4XHViMjk0LCBcdWMyYjlcdWM2ZDBcdWM3NzRcdWFjMDAgXHVjYzk4XHVjNzRjIFx1YWNiZFx1YzdjMVx1ZDU2MCBcdWI1NGMgXHVjMGJjXHVjNzQ0IFx1ZDQ1Y1x1YzgwMVx1Yzc1OCBcdWJjODhcdWQ2MzhcdWI5N2MgXHViNzNiXHVkNTVjXHViMmU0LiBcdWI5Y2NcdWM1N2RcdWM1ZDAgXHVjZDVjXHVjODAxXHVjNzU4IFx1YzcwNFx1Y2U1OFx1YWMwMCBcdWM1ZWNcdWI3ZWMgXHVhY2YzXHVjNzc0XHViNzdjXHViYTc0LCBcdWFkZjggXHVjOTExIFx1YWMwMFx1YzdhNSBcdWJjODhcdWQ2MzhcdWFjMDAgXHViMTkyXHVjNzQwIFx1YzcwNFx1Y2U1OFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWJhNzQgXHViNDFjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5cdWMyYjlcdWM2ZDBcdWM3NzRcdWM3NTggXHVjMmU0XHViODI1IFx1YjRmMVx1YWUwOVx1Yzc0MCA3XHVjNzc0XHViMmU0LiAxXHViYzg4IFx1ZDQ1Y1x1YzgwMVx1YzVkMFx1YzExYyBcdWMyZGNcdWM3OTFcdWQ1NjAgXHVhY2JkXHVjNmIwIFx1YzJiOVx1YzZkMFx1Yzc3NFx1YjI5NCA0XHViYzg4IFx1ZDQ1Y1x1YzgwMVx1YzczY1x1Yjg1YyBcdWFjMDQgXHVkNmM0IFx1YjA1ZFx1YWU0Y1x1YzljMCBcdWQ1NzRcdWIyZjkgXHVkNDVjXHVjODAxXHVjNWQwIFx1YmEzOFx1YmIzNFx1Yjk3OFx1YjJlNC4gMlx1YmM4OCBcdWQ0NWNcdWM4MDFcdWM3NzRcdWIwOTggNFx1YmM4OCBcdWQ0NWNcdWM4MDFcdWM1ZDBcdWMxMWMgXHVjMmRjXHVjNzkxXHVkNTYwIFx1YWNiZFx1YzZiMCBcdWMyYjlcdWM2ZDBcdWM3NzRcdWIyOTQgXHViMDVkXHVhZTRjXHVjOWMwIFx1ZDU3NFx1YjJmOSBcdWQ0NWNcdWM4MDFcdWM1ZDAgXHViYTM4XHViYjM0XHViOTc4XHViMmU0LiAzXHViYzg4IFx1ZDQ1Y1x1YzgwMVx1YzVkMFx1YzExYyBcdWMyZGNcdWM3OTFcdWQ1NjAgXHVhY2JkXHVjNmIwIFx1YzJiOVx1YzZkMFx1Yzc3NFx1YjI5NCBcdWMyZTRcdWI4MjUgXHViNGYxXHVhZTA5XHVjNzc0IDhcdWM3NzggXHVhZDgxXHVjMjE4XHViOTdjIFx1Yzc3NFx1YWUzMFx1YWNlMCAyXHViYzg4IFx1ZDQ1Y1x1YzgwMVx1YzVkMCBcdWIwNWRcdWFlNGNcdWM5YzAgXHViYTM4XHViYjM0XHViOTc4XHViMmU0LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNTQ2MCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkFyY2hlcnkiLCJkZXNjcmlwdGlvbiI6IjxwPkFuIGFyY2hlcnkgdG91cm5hbWVudCBpcyBoZWxkIGFjY29yZGluZyB0byB0aGUgZm9sbG93aW5nIHJ1bGVzLiBUaGVyZSBhcmUgTiB0YXJnZXRzIGFycmFuZ2VkIGluIGEgbGluZSBhbmQgbnVtYmVyZWQgZnJvbSAxIHRvIE4gaW5jbHVzaXZlIGFjY29yZGluZyB0byB0aGVpciBwbGFjZSBvbiB0aGUgbGluZSAodGhlIGxlZnRtb3N0IHRhcmdldCBiZWluZyB0YXJnZXQgMSwgYW5kIHRoZSByaWdodG1vc3QgdGFyZ2V0IGJlaW5nIHRhcmdldCBOKS4gVGhlcmUgYXJlIGFsc28gMipOIGFyY2hlcnMuIEF0IGFueSB0aW1lIGR1cmluZyB0aGUgdG91cm5hbWVudCwgdGhlcmUgYXJlIHR3byBhcmNoZXJzIG9uIGVhY2ggdGFyZ2V0LiBFdmVyeSByb3VuZCBvZiB0aGUgdG91cm5hbWVudCBnb2VzIGFjY29yZGluZyB0byB0aGUgZm9sbG93aW5nIHByb2NlZHVyZTo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5UaGUgdHdvIGFyY2hlcnMgb24gZWFjaCB0YXJnZXQgY29tcGV0ZSB3aXRoIGVhY2ggb3RoZXIgYW5kIGRldGVybWluZSBhIHdpbm5lciBhbmQgYSBsb3NlciBiZXR3ZWVuIHRoZW0uIFRoZW4gYWxsIGFyY2hlcnMgYXJlIHJlYXJyYW5nZWQgYXMgZm9sbG93czpcclxuXHQ8dWw+XHJcblx0XHQ8bGk+VGhlIHdpbm5lcnMgb24gdGFyZ2V0cyAyIHRvIE4gaW5jbHVzaXZlIG1vdmUgdG8gdGhlIHRhcmdldCBvbiB0aGVpciBsZWZ0IChpLmUuLCB0YXJnZXRzIDEgdG8gTiAtIDEgcmVzcGVjdGl2ZWx5KS48XC9saT5cclxuXHRcdDxsaT5UaGUgbG9zZXJzIG9uIHRhcmdldHMgMiB0byBOIGluY2x1c2l2ZSwgYXMgd2VsbCBhcyB0aGUgd2lubmVyIG9uIHRhcmdldCAxLCByZW1haW4gb24gdGhlIHNhbWUgdGFyZ2V0LjxcL2xpPlxyXG5cdFx0PGxpPlRoZSBsb3NlciBvbiB0YXJnZXQgMSBtb3ZlcyB0byB0YXJnZXQgTi48XC9saT5cclxuXHQ8XC91bD5cclxuXHQ8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5UaGUgdG91cm5hbWVudCBjb250aW51ZXMgZm9yIFIgcm91bmRzLCB3aXRoIHRoZSBudW1iZXIgb2Ygcm91bmRzIGJlaW5nIGF0IGxlYXN0IGFzIG1hbnkgYXMgdGhlIG51bWJlciBvZiBhcmNoZXJzIChpLmUuLCBSICZnZTsgMipOKS48XC9wPlxyXG5cclxuPHA+WW91IGFyZSB0aGUgb25seSBhcmNoZXIgdG8gYXJyaXZlIGZvciB0aGUgdG91cm5hbWVudCBleGFjdGx5IG9uIHRpbWUuIEFsbCBvdGhlciAyKk4gLSAxIGFyY2hlcnMgaGF2ZSBhcnJpdmVkIGVhcmx5IGFuZCBhcmUgYWxyZWFkeSBzdGFuZGluZyBpbiBhIGxpbmUuIFdoYXQgeW91IGhhdmUgdG8gZG8gbm93IGlzIHRvIGluc2VydCB5b3Vyc2VsZiBzb21ld2hlcmUgaW50byB0aGUgbGluZSBhbW9uZ3N0IHRoZW0uIFlvdSBrbm93IHRoYXQgYWZ0ZXIgeW91IHRha2UgeW91ciBwb3NpdGlvbiwgdGhlIHR3byBsZWZ0bW9zdCBhcmNoZXJzIGluIHRoZSBsaW5lIHdpbGwgc3RhcnQgdGhlIHRvdXJuYW1lbnQgb24gdGFyZ2V0IDEsIHRoZSBuZXh0IHR3byB3aWxsIHN0YXJ0IG9uIHRhcmdldCAyIGFuZCBzbyBvbiwgd2l0aCB0aGUgdHdvIHJpZ2h0bW9zdCBhcmNoZXJzIHN0YXJ0aW5nIG9uIHRhcmdldCBOLjxcL3A+XHJcblxyXG48cD5BbGwgdGhlIDIqTiBhcmNoZXJzIGluIHRoZSB0b3VybmFtZW50IChpbmNsdWRpbmcgeW91cnNlbGYpIGFyZSByYW5rZWQgYnkgc2tpbGwsIHdoZXJlIGEgc21hbGxlciByYW5rIGNvcnJlc3BvbmRzIHRvIGJldHRlciBza2lsbC4gTm8gdHdvIGFyY2hlcnMgaGF2ZSB0aGUgc2FtZSByYW5rLiBBbHNvLCB3aGVuZXZlciB0d28gYXJjaGVycyBjb21wZXRlLCB0aGUgb25lIHdpdGggdGhlIHNtYWxsZXIgcmFuayB3aWxsIGFsd2F5cyB3aW4uPFwvcD5cclxuXHJcbjxwPktub3dpbmcgaG93IHNraWxsZWQgZWFjaCBvZiB5b3VyIGNvbXBldGl0b3JzIGlzLCB5b3Ugd2FudCB0byBpbnNlcnQgeW91cnNlbGYgaW4gc3VjaCBhIHdheSBhcyB0byBlbnN1cmUgdGhhdCB5b3Ugd2lsbCBmaW5pc2ggdGhlIHRvdXJuYW1lbnQgb24gYSB0YXJnZXQgd2l0aCBhcyBzbWFsbCBhIG51bWJlciBhcyBwb3NzaWJsZS4gSWYgdGhlcmUgYXJlIG11bHRpcGxlIHdheXMgdG8gZG8gdGhpcywgeW91IHByZWZlciB0aGUgb25lIHRoYXQgc3RhcnRzIGF0IGEgdGFyZ2V0IHdpdGggYXMgbGFyZ2UgYSBudW1iZXIgYXMgcG9zc2libGUuJm5ic3A7PFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB0aGF0LCBnaXZlbiB0aGUgcmFua3Mgb2YgYWxsIGFyY2hlcnMsIGluY2x1ZGluZyB5b3Vyc2VsZiwgYXMgd2VsbCBhcyB5b3VyIGNvbXBldGl0b3JzJnJzcXVvOyBhcnJhbmdlbWVudCBvbiB0aGUgbGluZSwgZGV0ZXJtaW5lcyBvbiB3aGljaCB0YXJnZXQgeW91IHNob3VsZCBzdGFydCB0aGUgdG91cm5hbWVudCwgc28gdGhhdCB5b3UgY2FuIGFjaGlldmUgeW91ciBnb2FscyBhcyBkZWZpbmVkIGFib3ZlLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+WW91ciBwcm9ncmFtIG11c3QgcmVhZCBmcm9tIHN0YW5kYXJkIGlucHV0IHRoZSBmb2xsb3dpbmcgZGF0YTo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5UaGUgZmlyc3QgbGluZSBjb250YWlucyB0aGUgaW50ZWdlcnMgTiBhbmQgUiwgc2VwYXJhdGVkIGJ5IGEgc3BhY2UuPFwvbGk+XHJcblx0PGxpPlRoZSBuZXh0IDIqTiBsaW5lcyBsaXN0IHRoZSByYW5rcyBvZiB0aGUgYXJjaGVycy4gVGhlIGZpcnN0IG9mIHRoZXNlIGxpbmVzIGNvbnRhaW5zIHlvdXIgcmFuay4gVGhlIHJlc3Qgb2YgdGhlc2UgbGluZXMgY29udGFpbiB0aGUgcmFua3Mgb2YgdGhlIG90aGVyIGFyY2hlcnMsIG9uZSBhcmNoZXIgcGVyIGxpbmUsIGluIHRoZSBvcmRlciBpbiB3aGljaCB0aGV5IGhhdmUgYXJyYW5nZWQgdGhlbXNlbHZlcyAoZnJvbSBsZWZ0IHRvIHJpZ2h0KS4gRWFjaCBvZiB0aGVzZSAyKk4gbGluZXMgY29udGFpbnMgYSBzaW5nbGUgaW50ZWdlciBiZXR3ZWVuIDEgYW5kIDIqTiBpbmNsdXNpdmUuIEEgcmFuayBvZiAxIGlzIHRoZSBiZXN0IGFuZCBhIHJhbmsgb2YgMipOIGlzIHRoZSB3b3JzdC4gTm8gdHdvIGFyY2hlcnMgaGF2ZSB0aGUgc2FtZSByYW5rLjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+MSAmbGU7IE4gJmxlOyAyMDAsMDAwIFRoZSBudW1iZXIgb2YgdGFyZ2V0czsgYWxzbyBlcXVhbCB0byBoYWxmIHRoZSBudW1iZXIgb2YgYXJjaGVyczxcL2xpPlxyXG5cdDxsaT4yKk4gJmxlOyBSICZsZTsgMSwwMDAsMDAwLDAwMCBUaGUgbnVtYmVyIG9mIHRvdXJuYW1lbnQgcm91bmRzPFwvbGk+XHJcblx0PGxpPjEgJmxlOyBTayAmbGU7IDIqTiBUaGUgcmFuayBvZiBhcmNoZXIgazxcL2xpPlxyXG48XC91bD5cclxuIiwib3V0cHV0IjoiPHA+WW91ciBwcm9ncmFtIG11c3Qgd3JpdGUgdG8gc3RhbmRhcmQgb3V0cHV0IGEgc2luZ2xlIGxpbmUgY29udGFpbmluZyBhIHNpbmdsZSBpbnRlZ2VyIGJldHdlZW4gMSBhbmQgTiBpbmNsdXNpdmU6IHRoZSBudW1iZXIgb2YgdGhlIHRhcmdldCBvbiB3aGljaCB5b3Ugd2lsbCBzdGFydCB0aGUgdG91cm5hbWVudC4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiPHA+U2FtcGxlIDE8XC9wPlxyXG5cclxuPHA+WW91IGFyZSB0aGUgc2Vjb25kIHdvcnN0IGFyY2hlci4gSWYgeW91IHN0YXJ0IG9uIHRhcmdldCAxLCB5b3Ugd2lsbCB0aGVuIGdvIHRvIHRhcmdldCA0IGFuZCBzdGF5IHRoZXJlIHVudGlsIHRoZSBlbmQuIElmIHlvdSBzdGFydCBvbiB0YXJnZXQgMiBvciA0LCB5b3Ugd2lsbCBqdXN0IHN0YXkgdGhlcmUgZm9yIHRoZSB3aG9sZSB0b3VybmFtZW50LiBJZiB5b3Ugc3RhcnQgb24gdGFyZ2V0IDMsIHlvdSB3aWxsIGJlYXQgdGhlIHdvcnN0IGFyY2hlciBhbmQgdGhlbiBtb3ZlIHRvIHRhcmdldCAyIGFuZCBzdGF5IHRoZXJlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5TYW1wbGUgMjxcL3A+XHJcblxyXG48cD5Zb3UgYXJlIHRoZSBzZWNvbmQgYmVzdCBhcmNoZXIuIFRoZSBiZXN0IG9uZSBpcyBhbHJlYWR5IG9uIHRhcmdldCAxIGFuZCB3aWxsIHN0YXkgdGhlcmUgZm9yIHRoZSB3aG9sZSBkdXJhdGlvbiBvZiB0aGUgdG91cm5hbWVudC4gVGh1cywgbm8gbWF0dGVyIHdoZXJlIHlvdSBzdGFydCwgeW91IHdpbGwgYWx3YXlzIG1vdmUgZnJvbSB5b3VyIHRhcmdldCwgZ29pbmcgdGhyb3VnaCBhbGwgdGFyZ2V0cyBmcm9tIDQgdG8gMSBvdmVyIGFuZCBvdmVyIGFnYWluLiBJbiBvcmRlciBmb3IgeW91IHRvIGVuZCBvbiB0YXJnZXQgMSBhZnRlciA5IHRyYW5zaXRpb25zLCB5b3UgaGF2ZSB0byBzdGFydCBvbiB0YXJnZXQgMi4mbmJzcDs8XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

Olympiad > International Olympiad in Informatics > IOI 2009 1번

  • 문제를 번역한 사람: koosaga