시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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+IE4tMSBcdWQ0NWNcdWM4MDFcdWM3M2NcdWI4NWMpLCAyIH4gTiBcdWQ0NWNcdWM4MDFcdWM1ZDBcdWMxMWMgXHVkMzI4XHViYzMwXHVkNTVjIFx1YWQ4MVx1YzIxOFx1YjRlNFx1Yzc0MCBcdWFkZjggXHVjNzkwXHViOWFjXHVjNWQwIFx1YmEzOFx1YmIzNFx1Yjk3OFx1YjJlNC4gXHVjNzc0XHViNTRjIDFcdWJjODggXHVkNDVjXHVjODAxXHVjNWQwXHVjMTFjIFx1YzJiOVx1YjlhY1x1ZDU1YyBcdWFkODFcdWMyMThcdWIyOTQgXHVhZGY4IFx1Yzc5MFx1YjlhY1x1YzVkMCBcdWJhMzhcdWJiMzRcdWI5NzRcdWJhNzAsIDFcdWJjODggXHVkNDVjXHVjODAxXHVjNWQwXHVjMTFjIFx1ZDMyOFx1YmMzMFx1ZDU1YyBcdWFkODFcdWMyMThcdWIyOTQgTlx1YmM4OFx1YzlmOCBcdWQ0NWNcdWM4MDFcdWM3M2NcdWI4NWMgXHVjNzc0XHViM2Q5XHVkNTVjXHViMmU0LiBcdWM3NzQgXHVkMWEwXHViMTA4XHViYTNjXHVkMmI4XHViMjk0IFJcdWJjODggXHVjOWM0XHVkNTg5XHViNDE4XHViYTcwLCBSICZndDs9IDIqTlx1Yzc4NFx1Yzc3NCBcdWJjZjRcdWM3YTVcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWNiZFx1ZDVkOFx1Yzc4OFx1YjI5NCBcdWM1OTFcdWFkODEgXHVkNTc0XHVjMTI0XHVhYzAwIFx1YzJiOVx1YzZkMFx1Yzc3NFx1YjI5NCBcdWM3OTBcdWMyZTBcdWM3NDQgXHVkM2VjXHVkNTY4XHVjNWQwXHVjMTFjIFx1Yzc3NFx1YmM4OFx1YzVkMCBcdWNkOWNcdWM4MDRcdWQ1NThcdWIyOTQgXHVjNTkxXHVhZDgxIFx1YzEyMFx1YzIxOFx1Yzc1OCBcdWMyZTRcdWI4MjUgXHViNGYxXHVhZTA5XHVjNzQ0IFx1YmFhOFx1YjQ1MCBcdWM1NGNcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWFjMDEgXHVjMTIwXHVjMjE4XHVjNzU4IFx1YzJlNFx1YjgyNSBcdWI0ZjFcdWFlMDlcdWM3NDAgMSB+IDIqTiBcdWFlNGNcdWM5YzBcdWM3NTggXHVjMjE4XHViODVjIFx1ZDQ1Y1x1YzJkY1x1YjQxOFx1YmE3MCwgXHViNGYxXHVhZTA5XHVjNzc0IFx1YjBhZVx1Yzc0MCBcdWMxMjBcdWMyMThcdWM3N2NcdWMyMThcdWI4NWQgXHViNmYwXHVjNWI0XHViMDljIFx1YzEyMFx1YzIxOFx1Yzc3NFx1YjJlNC4gXHVjMmI5XHVjNmQwXHVjNzc0XHVjNzU4IFx1Yzc3NCBcdWIzNzBcdWM3NzRcdWQxMzBcdWIyOTQgXHVjODE1XHViOWQwIFx1YzgxNVx1ZDY1NVx1ZDU3NFx1YzExYywgXHVkNTZkXHVjMGMxIFx1YzJlNFx1YjgyNVx1Yzc3NCBcdWIxOTJcdWM3NDAgXHVjMTIwXHVjMjE4XHVhYzAwIFx1YzJlNFx1YjgyNVx1Yzc3NCBcdWIwYWVcdWM3NDAgXHVjMTIwXHVjMjE4XHViOTdjIFx1Yzc3NFx1YWUzNFx1YjJlNFx1YjI5NCBcdWMwYWNcdWMyZTRcdWM3NDQgXHViY2Y0XHVjN2E1XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YzJiOVx1YzZkMFx1Yzc3NFx1YjI5NCBcdWM1OTFcdWFkODEgXHVkNTc0XHVjMTI0XHVjNWQwIFx1ZDBjMFx1YWNlMFx1YjA5YyBcdWM3YWNcdWIyYTVcdWM3NDQgXHVhYzAwXHVjOWMwXHVhY2UwIFx1Yzc4OFx1YzljMFx1YjljYyBcdWM3NzRcdWMwYzFcdWQ1NThcdWFjOGMgXHVjNTkxXHVhZDgxIFx1Yzc5MFx1Y2NiNFx1YzVkMFx1YjI5NCBcdWJjYzQgXHVhZDAwXHVjMmVjXHVjNzc0IFx1YzVjNlx1YzViNFx1YzExYywgXHVjNzc0XHViYzg4IFx1YjMwMFx1ZDY4Y1x1YzVkMFx1YzExYyBcdWM3NzRcdWFlMzBcdWIyOTQgXHVhYzgzXHViY2Y0XHViMmU0XHViMjk0IFx1YzYyNFx1YjI5OCBcdWJjMjQgXHVjNzg4XHViMjk0IFx1Y2Y1NFx1YjRkY1x1ZDNlY1x1YzJhNCBcdWI3N2NcdWM2YjRcdWI0ZGNcdWI5N2MgXHViMTkzXHVjZTU4XHVjOWMwIFx1YzU0YVx1YjI5NCBcdWFjODNcdWM1ZDAgXHViMzU0IFx1YWQwMFx1YzJlY1x1Yzc3NCBcdWM3ODhcdWIyZTQuIFx1Y2Q5Y1x1YWQ2Y1x1YjI5NCBcdWI5ZTggXHVjNjdjXHVjYWJkXHVjNWQwIFx1Yzc4OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIFx1YzJiOVx1YzZkMFx1Yzc3NFx1YjI5NCBSXHViYzg4XHVjNzU4IFx1Yjc3Y1x1YzZiNFx1YjRkY1x1YWMwMCBcdWIwNWRcdWIwOThcdWFjZTAgXHViMDk4XHVjMTFjIFx1YWMwMFx1YzdhNSBcdWM2N2NcdWNhYmQgXHVkMGMwXHVhYzlmXHVjNWQwIFx1YzExYyBcdWM3ODhcdWFlMzBcdWI5N2MgXHVjNmQwXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWQ1ODlcdWM3NzRcdWIzYzQsIFx1YzJiOVx1YzZkMFx1Yzc3NFx1Yjk3YyBcdWM4MWNcdWM2NzhcdWQ1NWMgMipOLTFcdWJhODVcdWM3NTggXHVhZDgxXHVjMjE4XHVhYzAwIFx1YzVmMFx1YzJiNVx1Yzc0NCBcdWM3MDRcdWQ1NzQgXHVjNzdjXHVjYzBkIFx1YjMwMFx1ZDY4Y1x1YzdhNVx1YzVkMCBcdWIwOThcdWM2NDBcdWM3ODhcdWM1YzhcdWIyZTQuIFx1YzJiOVx1YzZkMFx1Yzc3NFx1YjI5NCBcdWM4MDFcdWM4MDhcdWQ1NWMgXHVjNzA0XHVjZTU4XHVjNWQwIFx1YjA3Y1x1YzViNFx1YjRlNFx1YzViNFx1YWMwMFx1YzExYyBcdWM1OTFcdWFkODEgXHVhY2JkXHVhZTMwXHViOTdjIFx1YzJkY1x1Yzc5MVx1ZDU1OFx1YjgyNCBcdWQ1NWNcdWIyZTQuIFx1YWNmY1x1YzVmMCBcdWMyYjlcdWM2ZDBcdWM3NzRcdWIyOTQgXHVjNWI0XHViNWEwXHVkNTVjIFx1YzcwNFx1Y2U1OFx1YzVkMCBcdWIwN2NcdWM1YjRcdWI0ZTRcdWM1YjRcdWFjMDBcdWM1N2NcdWM5YzAgXHVhYzAwXHVjN2E1IFx1Yzc3Y1x1Y2MwZCBcdWM5ZDFcdWM1ZDAgXHViNGU0XHVjNWI0XHVhYzA4IFx1YzIxOCBcdWM3ODhcdWM3NDRcdWFlNGM/PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWQ0NWNcdWM5MDAgXHVjNzg1XHViODI1XHVjNzNjXHViODVjXHViZDgwXHVkMTMwIFx1YjJlNFx1Yzc0Y1x1Yzc1OCBcdWIzNzBcdWM3NzRcdWQxMzBcdWI5N2MgXHVjNzdkXHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNCA6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDAgTlx1YWNmYyBSXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9saT5cclxuXHQ8bGk+XHViNDUwIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjMmI5XHVjNmQwXHVjNzc0XHVjNzU4IFx1YzJlNFx1YjgyNSBcdWI0ZjFcdWFlMDlcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWMxMzggXHViYzg4XHVjOWY4IFx1YzkwNCBcdWM3NzRcdWQ2YzQgMipOLTFcdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwIFx1YWMwMSBcdWMxMjBcdWMyMThcdWM3NTggXHVjMmU0XHViODI1IFx1YjRmMVx1YWUwOVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1ZDYwNFx1YzdhYyBcdWMxMjBcdWMyMThcdWI0ZTRcdWM3NDAgXHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0IFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWM2N2NcdWNhYmRcdWM1ZDBcdWMxMWMgXHVjNjI0XHViOTc4XHVjYWJkXHVjNzNjXHViODVjIFx1YzExYyBcdWM3ODhcdWIyZTQuIFx1Yzk4OSBcdWMxMzggXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM4MDFcdWQ2MDBcdWM3ODhcdWIyOTQgXHVjMTIwXHVjMjE4XHVhYzAwIFx1YWMwMFx1YzdhNSBcdWM2N2NcdWNhYmRcdWM1ZDAgXHVjNzg4XHVjNzNjXHViYTcwLCAyKk4rMVx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjODAxXHVkNjAwXHVjNzg4XHViMjk0IFx1YzEyMFx1YzIxOFx1YWMwMCBcdWFjMDBcdWM3YTUgXHVjNjI0XHViOTc4XHVjYWJkXHVjNWQwIFx1Yzc4OFx1YjJlNC4gXHVjMmU0XHViODI1IFx1YjRmMVx1YWUwOVx1Yzc0MCAyKk4gXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWM3NDAgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCBcdWM3OTBcdWM1ZjBcdWMyMThcdWM3NzRcdWIyZTQuPFwvbGk+XHJcblx0PGxpPjEgJmx0Oz0gTiAmbHQ7PSAyMDAwMDA8XC9saT5cclxuXHQ8bGk+MipOICZsdDs9IFIgJmx0Oz0gMSwwMDAsMDAwLDAwMDxcL2xpPlxyXG48XC91bD5cclxuIiwib3V0cHV0IjoiPHA+XHVjMmI5XHVjNmQwXHVjNzc0XHVhYzAwIFx1YzlkMVx1YzVkMCBcdWM3N2NcdWNjMGQgXHViNGU0XHVjNWI0XHVhYzAwXHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWIwN2NcdWM1YjRcdWI0ZTRcdWM1YjRcdWFjMDBcdWM1N2MgXHVkNTYwIFx1YzcwNFx1Y2U1OFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1Yzc3NFx1YjU0YyBcdWM3MDRcdWNlNThcdWIyOTQsIFx1YzJiOVx1YzZkMFx1Yzc3NFx1YWMwMCBcdWNjOThcdWM3NGMgXHVhY2JkXHVjN2MxXHVkNTYwIFx1YjU0YyBcdWMwYmNcdWM3NDQgXHVkNDVjXHVjODAxXHVjNzU4IFx1YmM4OFx1ZDYzOFx1Yjk3YyBcdWI3M2JcdWQ1NWNcdWIyZTQuIFx1YjljY1x1YzU3ZFx1YzVkMCBcdWNkNWNcdWM4MDFcdWM3NTggXHVjNzA0XHVjZTU4XHVhYzAwIFx1YzVlY1x1YjdlYyBcdWFjZjNcdWM3NzRcdWI3N2NcdWJhNzQsIFx1YWRmOCBcdWM5MTEgXHVhYzAwXHVjN2E1IFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWIxOTJcdWM3NDAgXHVjNzA0XHVjZTU4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YmE3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPlx1YzJiOVx1YzZkMFx1Yzc3NFx1Yzc1OCBcdWMyZTRcdWI4MjUgXHViNGYxXHVhZTA5XHVjNzQwIDdcdWM3NzRcdWIyZTQuIDFcdWJjODggXHVkNDVjXHVjODAxXHVjNWQwXHVjMTFjIFx1YzJkY1x1Yzc5MVx1ZDU2MCBcdWFjYmRcdWM2YjAgXHVjMmI5XHVjNmQwXHVjNzc0XHViMjk0IDRcdWJjODggXHVkNDVjXHVjODAxXHVjNzNjXHViODVjIFx1YWMwNCBcdWQ2YzQgXHViMDVkXHVhZTRjXHVjOWMwIFx1ZDU3NFx1YjJmOSBcdWQ0NWNcdWM4MDFcdWM1ZDAgXHViYTM4XHViYjM0XHViOTc4XHViMmU0LiAyXHViYzg4IFx1ZDQ1Y1x1YzgwMVx1Yzc3NFx1YjA5OCA0XHViYzg4IFx1ZDQ1Y1x1YzgwMVx1YzVkMFx1YzExYyBcdWMyZGNcdWM3OTFcdWQ1NjAgXHVhY2JkXHVjNmIwIFx1YzJiOVx1YzZkMFx1Yzc3NFx1YjI5NCBcdWIwNWRcdWFlNGNcdWM5YzAgXHVkNTc0XHViMmY5IFx1ZDQ1Y1x1YzgwMVx1YzVkMCBcdWJhMzhcdWJiMzRcdWI5NzhcdWIyZTQuIDNcdWJjODggXHVkNDVjXHVjODAxXHVjNWQwXHVjMTFjIFx1YzJkY1x1Yzc5MVx1ZDU2MCBcdWFjYmRcdWM2YjAgXHVjMmI5XHVjNmQwXHVjNzc0XHViMjk0IFx1YzJlNFx1YjgyNSBcdWI0ZjFcdWFlMDlcdWM3NzQgOFx1Yzc3OCBcdWFkODFcdWMyMThcdWI5N2MgXHVjNzc0XHVhZTMwXHVhY2UwIDJcdWJjODggXHVkNDVjXHVjODAxXHVjNWQwIFx1YjA1ZFx1YWU0Y1x1YzljMCBcdWJhMzhcdWJiMzRcdWI5NzhcdWIyZTQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI1NDYwIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQXJjaGVyeSIsImRlc2NyaXB0aW9uIjoiPHA+QW4gYXJjaGVyeSB0b3VybmFtZW50IGlzIGhlbGQgYWNjb3JkaW5nIHRvIHRoZSBmb2xsb3dpbmcgcnVsZXMuIFRoZXJlIGFyZSBOIHRhcmdldHMgYXJyYW5nZWQgaW4gYSBsaW5lIGFuZCBudW1iZXJlZCBmcm9tIDEgdG8gTiBpbmNsdXNpdmUgYWNjb3JkaW5nIHRvIHRoZWlyIHBsYWNlIG9uIHRoZSBsaW5lICh0aGUgbGVmdG1vc3QgdGFyZ2V0IGJlaW5nIHRhcmdldCAxLCBhbmQgdGhlIHJpZ2h0bW9zdCB0YXJnZXQgYmVpbmcgdGFyZ2V0IE4pLiBUaGVyZSBhcmUgYWxzbyAyKk4gYXJjaGVycy4gQXQgYW55IHRpbWUgZHVyaW5nIHRoZSB0b3VybmFtZW50LCB0aGVyZSBhcmUgdHdvIGFyY2hlcnMgb24gZWFjaCB0YXJnZXQuIEV2ZXJ5IHJvdW5kIG9mIHRoZSB0b3VybmFtZW50IGdvZXMgYWNjb3JkaW5nIHRvIHRoZSBmb2xsb3dpbmcgcHJvY2VkdXJlOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlRoZSB0d28gYXJjaGVycyBvbiBlYWNoIHRhcmdldCBjb21wZXRlIHdpdGggZWFjaCBvdGhlciBhbmQgZGV0ZXJtaW5lIGEgd2lubmVyIGFuZCBhIGxvc2VyIGJldHdlZW4gdGhlbS4gVGhlbiBhbGwgYXJjaGVycyBhcmUgcmVhcnJhbmdlZCBhcyBmb2xsb3dzOlxyXG5cdDx1bD5cclxuXHRcdDxsaT5UaGUgd2lubmVycyBvbiB0YXJnZXRzIDIgdG8gTiBpbmNsdXNpdmUgbW92ZSB0byB0aGUgdGFyZ2V0IG9uIHRoZWlyIGxlZnQgKGkuZS4sIHRhcmdldHMgMSB0byBOIC0gMSByZXNwZWN0aXZlbHkpLjxcL2xpPlxyXG5cdFx0PGxpPlRoZSBsb3NlcnMgb24gdGFyZ2V0cyAyIHRvIE4gaW5jbHVzaXZlLCBhcyB3ZWxsIGFzIHRoZSB3aW5uZXIgb24gdGFyZ2V0IDEsIHJlbWFpbiBvbiB0aGUgc2FtZSB0YXJnZXQuPFwvbGk+XHJcblx0XHQ8bGk+VGhlIGxvc2VyIG9uIHRhcmdldCAxIG1vdmVzIHRvIHRhcmdldCBOLjxcL2xpPlxyXG5cdDxcL3VsPlxyXG5cdDxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlRoZSB0b3VybmFtZW50IGNvbnRpbnVlcyBmb3IgUiByb3VuZHMsIHdpdGggdGhlIG51bWJlciBvZiByb3VuZHMgYmVpbmcgYXQgbGVhc3QgYXMgbWFueSBhcyB0aGUgbnVtYmVyIG9mIGFyY2hlcnMgKGkuZS4sIFIgJmdlOyAyKk4pLjxcL3A+XHJcblxyXG48cD5Zb3UgYXJlIHRoZSBvbmx5IGFyY2hlciB0byBhcnJpdmUgZm9yIHRoZSB0b3VybmFtZW50IGV4YWN0bHkgb24gdGltZS4gQWxsIG90aGVyIDIqTiAtIDEgYXJjaGVycyBoYXZlIGFycml2ZWQgZWFybHkgYW5kIGFyZSBhbHJlYWR5IHN0YW5kaW5nIGluIGEgbGluZS4gV2hhdCB5b3UgaGF2ZSB0byBkbyBub3cgaXMgdG8gaW5zZXJ0IHlvdXJzZWxmIHNvbWV3aGVyZSBpbnRvIHRoZSBsaW5lIGFtb25nc3QgdGhlbS4gWW91IGtub3cgdGhhdCBhZnRlciB5b3UgdGFrZSB5b3VyIHBvc2l0aW9uLCB0aGUgdHdvIGxlZnRtb3N0IGFyY2hlcnMgaW4gdGhlIGxpbmUgd2lsbCBzdGFydCB0aGUgdG91cm5hbWVudCBvbiB0YXJnZXQgMSwgdGhlIG5leHQgdHdvIHdpbGwgc3RhcnQgb24gdGFyZ2V0IDIgYW5kIHNvIG9uLCB3aXRoIHRoZSB0d28gcmlnaHRtb3N0IGFyY2hlcnMgc3RhcnRpbmcgb24gdGFyZ2V0IE4uPFwvcD5cclxuXHJcbjxwPkFsbCB0aGUgMipOIGFyY2hlcnMgaW4gdGhlIHRvdXJuYW1lbnQgKGluY2x1ZGluZyB5b3Vyc2VsZikgYXJlIHJhbmtlZCBieSBza2lsbCwgd2hlcmUgYSBzbWFsbGVyIHJhbmsgY29ycmVzcG9uZHMgdG8gYmV0dGVyIHNraWxsLiBObyB0d28gYXJjaGVycyBoYXZlIHRoZSBzYW1lIHJhbmsuIEFsc28sIHdoZW5ldmVyIHR3byBhcmNoZXJzIGNvbXBldGUsIHRoZSBvbmUgd2l0aCB0aGUgc21hbGxlciByYW5rIHdpbGwgYWx3YXlzIHdpbi48XC9wPlxyXG5cclxuPHA+S25vd2luZyBob3cgc2tpbGxlZCBlYWNoIG9mIHlvdXIgY29tcGV0aXRvcnMgaXMsIHlvdSB3YW50IHRvIGluc2VydCB5b3Vyc2VsZiBpbiBzdWNoIGEgd2F5IGFzIHRvIGVuc3VyZSB0aGF0IHlvdSB3aWxsIGZpbmlzaCB0aGUgdG91cm5hbWVudCBvbiBhIHRhcmdldCB3aXRoIGFzIHNtYWxsIGEgbnVtYmVyIGFzIHBvc3NpYmxlLiBJZiB0aGVyZSBhcmUgbXVsdGlwbGUgd2F5cyB0byBkbyB0aGlzLCB5b3UgcHJlZmVyIHRoZSBvbmUgdGhhdCBzdGFydHMgYXQgYSB0YXJnZXQgd2l0aCBhcyBsYXJnZSBhIG51bWJlciBhcyBwb3NzaWJsZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRoYXQsIGdpdmVuIHRoZSByYW5rcyBvZiBhbGwgYXJjaGVycywgaW5jbHVkaW5nIHlvdXJzZWxmLCBhcyB3ZWxsIGFzIHlvdXIgY29tcGV0aXRvcnMmcnNxdW87IGFycmFuZ2VtZW50IG9uIHRoZSBsaW5lLCBkZXRlcm1pbmVzIG9uIHdoaWNoIHRhcmdldCB5b3Ugc2hvdWxkIHN0YXJ0IHRoZSB0b3VybmFtZW50LCBzbyB0aGF0IHlvdSBjYW4gYWNoaWV2ZSB5b3VyIGdvYWxzIGFzIGRlZmluZWQgYWJvdmUuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5Zb3VyIHByb2dyYW0gbXVzdCByZWFkIGZyb20gc3RhbmRhcmQgaW5wdXQgdGhlIGZvbGxvd2luZyBkYXRhOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIHRoZSBpbnRlZ2VycyBOIGFuZCBSLCBzZXBhcmF0ZWQgYnkgYSBzcGFjZS48XC9saT5cclxuXHQ8bGk+VGhlIG5leHQgMipOIGxpbmVzIGxpc3QgdGhlIHJhbmtzIG9mIHRoZSBhcmNoZXJzLiBUaGUgZmlyc3Qgb2YgdGhlc2UgbGluZXMgY29udGFpbnMgeW91ciByYW5rLiBUaGUgcmVzdCBvZiB0aGVzZSBsaW5lcyBjb250YWluIHRoZSByYW5rcyBvZiB0aGUgb3RoZXIgYXJjaGVycywgb25lIGFyY2hlciBwZXIgbGluZSwgaW4gdGhlIG9yZGVyIGluIHdoaWNoIHRoZXkgaGF2ZSBhcnJhbmdlZCB0aGVtc2VsdmVzIChmcm9tIGxlZnQgdG8gcmlnaHQpLiBFYWNoIG9mIHRoZXNlIDIqTiBsaW5lcyBjb250YWlucyBhIHNpbmdsZSBpbnRlZ2VyIGJldHdlZW4gMSBhbmQgMipOIGluY2x1c2l2ZS4gQSByYW5rIG9mIDEgaXMgdGhlIGJlc3QgYW5kIGEgcmFuayBvZiAyKk4gaXMgdGhlIHdvcnN0LiBObyB0d28gYXJjaGVycyBoYXZlIHRoZSBzYW1lIHJhbmsuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHVsPlxyXG5cdDxsaT4xICZsZTsgTiAmbGU7IDIwMCwwMDAgVGhlIG51bWJlciBvZiB0YXJnZXRzOyBhbHNvIGVxdWFsIHRvIGhhbGYgdGhlIG51bWJlciBvZiBhcmNoZXJzPFwvbGk+XHJcblx0PGxpPjIqTiAmbGU7IFIgJmxlOyAxLDAwMCwwMDAsMDAwIFRoZSBudW1iZXIgb2YgdG91cm5hbWVudCByb3VuZHM8XC9saT5cclxuXHQ8bGk+MSAmbGU7IFNrICZsZTsgMipOIFRoZSByYW5rIG9mIGFyY2hlciBrPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJvdXRwdXQiOiI8cD5Zb3VyIHByb2dyYW0gbXVzdCB3cml0ZSB0byBzdGFuZGFyZCBvdXRwdXQgYSBzaW5nbGUgbGluZSBjb250YWluaW5nIGEgc2luZ2xlIGludGVnZXIgYmV0d2VlbiAxIGFuZCBOIGluY2x1c2l2ZTogdGhlIG51bWJlciBvZiB0aGUgdGFyZ2V0IG9uIHdoaWNoIHlvdSB3aWxsIHN0YXJ0IHRoZSB0b3VybmFtZW50LiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiI8cD5TYW1wbGUgMTxcL3A+XHJcblxyXG48cD5Zb3UgYXJlIHRoZSBzZWNvbmQgd29yc3QgYXJjaGVyLiBJZiB5b3Ugc3RhcnQgb24gdGFyZ2V0IDEsIHlvdSB3aWxsIHRoZW4gZ28gdG8gdGFyZ2V0IDQgYW5kIHN0YXkgdGhlcmUgdW50aWwgdGhlIGVuZC4gSWYgeW91IHN0YXJ0IG9uIHRhcmdldCAyIG9yIDQsIHlvdSB3aWxsIGp1c3Qgc3RheSB0aGVyZSBmb3IgdGhlIHdob2xlIHRvdXJuYW1lbnQuIElmIHlvdSBzdGFydCBvbiB0YXJnZXQgMywgeW91IHdpbGwgYmVhdCB0aGUgd29yc3QgYXJjaGVyIGFuZCB0aGVuIG1vdmUgdG8gdGFyZ2V0IDIgYW5kIHN0YXkgdGhlcmUuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlNhbXBsZSAyPFwvcD5cclxuXHJcbjxwPllvdSBhcmUgdGhlIHNlY29uZCBiZXN0IGFyY2hlci4gVGhlIGJlc3Qgb25lIGlzIGFscmVhZHkgb24gdGFyZ2V0IDEgYW5kIHdpbGwgc3RheSB0aGVyZSBmb3IgdGhlIHdob2xlIGR1cmF0aW9uIG9mIHRoZSB0b3VybmFtZW50LiBUaHVzLCBubyBtYXR0ZXIgd2hlcmUgeW91IHN0YXJ0LCB5b3Ugd2lsbCBhbHdheXMgbW92ZSBmcm9tIHlvdXIgdGFyZ2V0LCBnb2luZyB0aHJvdWdoIGFsbCB0YXJnZXRzIGZyb20gNCB0byAxIG92ZXIgYW5kIG92ZXIgYWdhaW4uIEluIG9yZGVyIGZvciB5b3UgdG8gZW5kIG9uIHRhcmdldCAxIGFmdGVyIDkgdHJhbnNpdGlvbnMsIHlvdSBoYXZlIHRvIHN0YXJ0IG9uIHRhcmdldCAyLiZuYnNwOzxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

Olympiad > International Olympiad in Informatics > IOI 2009 1번

  • 문제를 번역한 사람: koosaga
  • 문제의 오타를 찾은 사람: sky1357