시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB158770.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번 표적에 끝까지 머무른다.

W3sicHJvYmxlbV9pZCI6IjU0NjAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM1OTFcdWFkODEiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzdhY1x1ZDYwNFx1Yzc3NFx1YjI5NCBcdWM1YmNcdWI5YzggXHVjODA0IFx1ZDFhMFx1YjEwOFx1YmEzY1x1ZDJiOCBcdWQ2MTVcdWQwZGNcdWM3NTggXHVjNTkxXHVhZDgxIFx1YjMwMFx1ZDY4Y1x1Yjk3YyBcdWM1ZjRcdWM1YzhcdWIyZTQuIDFcdWJjODhcdWJkODBcdWQxMzAgTlx1YmM4OFx1YWU0Y1x1YzljMCBcdWJjODhcdWQ2MzhcdWFjMDAgXHViOWU0XHVhY2E4XHVjOWM0IE5cdWFjMWNcdWM3NTggXHVkNDVjXHVjODAxXHVjNzc0IFx1Yzc3Y1x1YzljMVx1YzEyMFx1YzBjMVx1YzVkMCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgKFx1YWMwMFx1YzdhNSBcdWM4OGNcdWNlMjFcdWM1ZDAgMVx1YmM4OFx1YmQ4MFx1ZDEzMCBcdWMyZGNcdWM3OTFcdWQ1NThcdWM1ZWMgXHVjNjI0XHViOTc4XHVjYWJkXHVjNWQwIE5cdWJjODhcdWM3M2NcdWI4NWMgXHViMDVkXHViMDljXHViMmU0LikgXHViMDk4XHVjNWY0XHViNDE4XHVjNWI0IFx1Yzc4OFx1YzczY1x1YmE3MCwgMiZ0aW1lcztOIFx1YmE4NVx1Yzc1OCBcdWFkODFcdWMyMThcdWI0ZTRcdWM3NzQgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQxYTBcdWIxMDhcdWJhM2NcdWQyYjhcdWIyOTQgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc3NCBcdWM5YzRcdWQ1ODlcdWI0MWNcdWIyZTQgLSBcdWQ1NWMgXHVkNDVjXHVjODAxXHVjNWQwXHViMjk0IFx1ZDU2ZFx1YzBjMSAyXHViYTg1XHVjNzU4IFx1YWQ4MVx1YzIxOFx1YjRlNFx1Yzc3NCBcdWQ1NjBcdWIyZjlcdWI0MThcdWM1YjQgXHVjNzg4XHVjNzNjXHViYTcwLCBcdWI0NTAgXHVhZDgxXHVjMjE4XHViMjk0IFx1ZDU1YyBcdWQ0NWNcdWM4MDFcdWM3NDQgXHViNDUwXHVhY2UwIFx1YWNiZFx1YzdjMVx1ZDU1OFx1YmE3MCBcdWMyYjlcdWM3OTBcdWM2NDAgXHVkMzI4XHVjNzkwXHViOTdjIFx1YWMwMFx1Yjk3OFx1YjJlNC4gXHVjMmI5XHVjNzkwXHVjNjQwIFx1ZDMyOFx1Yzc5MFx1YWMwMCBcdWFjYjBcdWM4MTVcdWI0MWMgXHVkNmM0XHVjNWQwXHViMjk0LCAyIH4gTiBcdWQ0NWNcdWM4MDFcdWM1ZDBcdWMxMWMgXHVjMmI5XHViOWFjXHVkNTVjIFx1YWQ4MVx1YzIxOFx1YjRlNFx1Yzc3NCBcdWM2N2NcdWNhYmQgXHVkNDVjXHVjODAxXHVjNzNjXHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU1OFx1YmE3MCAoMSB+IE4tMSBcdWQ0NWNcdWM4MDFcdWM3M2NcdWI4NWMpLCAyIH4gTiBcdWQ0NWNcdWM4MDFcdWM1ZDBcdWMxMWMgXHVkMzI4XHViYzMwXHVkNTVjIFx1YWQ4MVx1YzIxOFx1YjRlNFx1Yzc0MCBcdWFkZjggXHVjNzkwXHViOWFjXHVjNWQwIFx1YmEzOFx1YmIzNFx1Yjk3OFx1YjJlNC4gXHVjNzc0XHViNTRjIDFcdWJjODggXHVkNDVjXHVjODAxXHVjNWQwXHVjMTFjIFx1YzJiOVx1YjlhY1x1ZDU1YyBcdWFkODFcdWMyMThcdWIyOTQgXHVhZGY4IFx1Yzc5MFx1YjlhY1x1YzVkMCBcdWJhMzhcdWJiMzRcdWI5NzRcdWJhNzAsIDFcdWJjODggXHVkNDVjXHVjODAxXHVjNWQwXHVjMTFjIFx1ZDMyOFx1YmMzMFx1ZDU1YyBcdWFkODFcdWMyMThcdWIyOTQgTlx1YmM4OFx1YzlmOCBcdWQ0NWNcdWM4MDFcdWM3M2NcdWI4NWMgXHVjNzc0XHViM2Q5XHVkNTVjXHViMmU0LiBcdWM3NzQgXHVkMWEwXHViMTA4XHViYTNjXHVkMmI4XHViMjk0IFJcdWJjODggXHVjOWM0XHVkNTg5XHViNDE4XHViYTcwLCBSICZnZTsgMiZ0aW1lcztOXHVjNzg0XHVjNzc0IFx1YmNmNFx1YzdhNVx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhY2JkXHVkNWQ4XHVjNzg4XHViMjk0IFx1YzU5MVx1YWQ4MSBcdWQ1NzRcdWMxMjRcdWFjMDAgXHVjMmI5XHVjNmQwXHVjNzc0XHViMjk0IFx1Yzc5MFx1YzJlMFx1Yzc0NCBcdWQzZWNcdWQ1NjhcdWM1ZDBcdWMxMWMgXHVjNzc0XHViYzg4XHVjNWQwIFx1Y2Q5Y1x1YzgwNFx1ZDU1OFx1YjI5NCBcdWM1OTFcdWFkODEgXHVjMTIwXHVjMjE4XHVjNzU4IFx1YzJlNFx1YjgyNSBcdWI0ZjFcdWFlMDlcdWM3NDQgXHViYWE4XHViNDUwIFx1YzU0Y1x1YWNlMCBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWMxMjBcdWMyMThcdWM3NTggXHVjMmU0XHViODI1IFx1YjRmMVx1YWUwOVx1Yzc0MCAxIH4gMiZ0aW1lcztOIFx1YWU0Y1x1YzljMFx1Yzc1OCBcdWMyMThcdWI4NWMgXHVkNDVjXHVjMmRjXHViNDE4XHViYTcwLCBcdWI0ZjFcdWFlMDlcdWM3NzQgXHViMGFlXHVjNzQwIFx1YzEyMFx1YzIxOFx1Yzc3Y1x1YzIxOFx1Yjg1ZCBcdWI2ZjBcdWM1YjRcdWIwOWMgXHVjMTIwXHVjMjE4XHVjNzc0XHViMmU0LiBcdWMyYjlcdWM2ZDBcdWM3NzRcdWM3NTggXHVjNzc0IFx1YjM3MFx1Yzc3NFx1ZDEzMFx1YjI5NCBcdWM4MTVcdWI5ZDAgXHVjODE1XHVkNjU1XHVkNTc0XHVjMTFjLCBcdWQ1NmRcdWMwYzEgXHVjMmU0XHViODI1XHVjNzc0IFx1YjE5Mlx1Yzc0MCBcdWMxMjBcdWMyMThcdWFjMDAgXHVjMmU0XHViODI1XHVjNzc0IFx1YjBhZVx1Yzc0MCBcdWMxMjBcdWMyMThcdWI5N2MgXHVjNzc0XHVhZTM0XHViMmU0XHViMjk0IFx1YzBhY1x1YzJlNFx1Yzc0NCBcdWJjZjRcdWM3YTVcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjMmI5XHVjNmQwXHVjNzc0XHViMjk0IFx1YzU5MVx1YWQ4MSBcdWQ1NzRcdWMxMjRcdWM1ZDAgXHVkMGMwXHVhY2UwXHViMDljIFx1YzdhY1x1YjJhNVx1Yzc0NCBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHVjOWMwXHViOWNjIFx1Yzc3NFx1YzBjMVx1ZDU1OFx1YWM4YyBcdWM1OTFcdWFkODEgXHVjNzkwXHVjY2I0XHVjNWQwXHViMjk0IFx1YmNjNCBcdWFkMDBcdWMyZWNcdWM3NzQgXHVjNWM2XHVjNWI0XHVjMTFjLCBcdWM3NzRcdWJjODggXHViMzAwXHVkNjhjXHVjNWQwXHVjMTFjIFx1Yzc3NFx1YWUzMFx1YjI5NCBcdWFjODNcdWJjZjRcdWIyZTRcdWIyOTQgXHVjNjI0XHViMjk4IFx1YmMyNCBcdWM3ODhcdWIyOTQgXHVjZjU0XHViNGRjXHVkM2VjXHVjMmE0IFx1Yjc3Y1x1YzZiNFx1YjRkY1x1Yjk3YyBcdWIxOTNcdWNlNThcdWM5YzAgXHVjNTRhXHViMjk0IFx1YWM4M1x1YzVkMCBcdWIzNTQgXHVhZDAwXHVjMmVjXHVjNzc0IFx1Yzc4OFx1YjJlNC4gXHVjZDljXHVhZDZjXHViMjk0IFx1YjllOCBcdWM2N2NcdWNhYmRcdWM1ZDAgXHVjNzg4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgXHVjMmI5XHVjNmQwXHVjNzc0XHViMjk0IFJcdWJjODhcdWM3NTggXHViNzdjXHVjNmI0XHViNGRjXHVhYzAwIFx1YjA1ZFx1YjA5OFx1YWNlMCBcdWIwOThcdWMxMWMgXHVhYzAwXHVjN2E1IFx1YzY3Y1x1Y2FiZCBcdWQwYzBcdWFjOWZcdWM1ZDAgXHVjMTFjIFx1Yzc4OFx1YWUzMFx1Yjk3YyBcdWM2ZDBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1ZDU4OVx1Yzc3NFx1YjNjNCwgXHVjMmI5XHVjNmQwXHVjNzc0XHViOTdjIFx1YzgxY1x1YzY3OFx1ZDU1YyAyJnRpbWVzO04tMVx1YmE4NVx1Yzc1OCBcdWFkODFcdWMyMThcdWFjMDAgXHVjNWYwXHVjMmI1XHVjNzQ0IFx1YzcwNFx1ZDU3NCBcdWM3N2NcdWNjMGQgXHViMzAwXHVkNjhjXHVjN2E1XHVjNWQwIFx1YjA5OFx1YzY0MFx1Yzc4OFx1YzVjOFx1YjJlNC4gXHVjMmI5XHVjNmQwXHVjNzc0XHViMjk0IFx1YzgwMVx1YzgwOFx1ZDU1YyBcdWM3MDRcdWNlNThcdWM1ZDAgXHViMDdjXHVjNWI0XHViNGU0XHVjNWI0XHVhYzAwXHVjMTFjIFx1YzU5MVx1YWQ4MSBcdWFjYmRcdWFlMzBcdWI5N2MgXHVjMmRjXHVjNzkxXHVkNTU4XHViODI0IFx1ZDU1Y1x1YjJlNC4gXHVhY2ZjXHVjNWYwIFx1YzJiOVx1YzZkMFx1Yzc3NFx1YjI5NCBcdWM1YjRcdWI1YTBcdWQ1NWMgXHVjNzA0XHVjZTU4XHVjNWQwIFx1YjA3Y1x1YzViNFx1YjRlNFx1YzViNFx1YWMwMFx1YzU3Y1x1YzljMCBcdWFjMDBcdWM3YTUgXHVjNzdjXHVjYzBkIFx1YzlkMVx1YzVkMCBcdWI0ZTRcdWM1YjRcdWFjMDggXHVjMjE4IFx1Yzc4OFx1Yzc0NFx1YWU0Yz88XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1ZDQ1Y1x1YzkwMCBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWNcdWJkODBcdWQxMzAgXHViMmU0XHVjNzRjXHVjNzU4IFx1YjM3MFx1Yzc3NFx1ZDEzMFx1Yjk3YyBcdWM3N2RcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0IDo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCBOXHVhY2ZjIFJcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWI0NTAgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMyYjlcdWM2ZDBcdWM3NzRcdWM3NTggXHVjMmU0XHViODI1IFx1YjRmMVx1YWUwOVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YzEzOCBcdWJjODhcdWM5ZjggXHVjOTA0IFx1Yzc3NFx1ZDZjNCAyJnRpbWVzO04tMVx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVhYzAxIFx1YzEyMFx1YzIxOFx1Yzc1OCBcdWMyZTRcdWI4MjUgXHViNGYxXHVhZTA5XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVkNjA0XHVjN2FjIFx1YzEyMFx1YzIxOFx1YjRlNFx1Yzc0MCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWIyOTQgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YzY3Y1x1Y2FiZFx1YzVkMFx1YzExYyBcdWM2MjRcdWI5NzhcdWNhYmRcdWM3M2NcdWI4NWMgXHVjMTFjIFx1Yzc4OFx1YjJlNC4gXHVjOTg5IFx1YzEzOCBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzgwMVx1ZDYwMFx1Yzc4OFx1YjI5NCBcdWMxMjBcdWMyMThcdWFjMDAgXHVhYzAwXHVjN2E1IFx1YzY3Y1x1Y2FiZFx1YzVkMCBcdWM3ODhcdWM3M2NcdWJhNzAsIDImdGltZXM7TisxXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM4MDFcdWQ2MDBcdWM3ODhcdWIyOTQgXHVjMTIwXHVjMjE4XHVhYzAwIFx1YWMwMFx1YzdhNSBcdWM2MjRcdWI5NzhcdWNhYmRcdWM1ZDAgXHVjNzg4XHViMmU0LiBcdWMyZTRcdWI4MjUgXHViNGYxXHVhZTA5XHVjNzQwIDImdGltZXM7TiBcdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1Yzc0MCBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1Yzc5MFx1YzVmMFx1YzIxOFx1Yzc3NFx1YjJlNC48XC9saT5cclxuPFwvdWw+XHJcbiIsIm91dHB1dCI6IjxwPlx1YzJiOVx1YzZkMFx1Yzc3NFx1YWMwMCBcdWM5ZDFcdWM1ZDAgXHVjNzdjXHVjYzBkIFx1YjRlNFx1YzViNFx1YWMwMFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHViMDdjXHVjNWI0XHViNGU0XHVjNWI0XHVhYzAwXHVjNTdjIFx1ZDU2MCBcdWM3MDRcdWNlNThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWM3NzRcdWI1NGMgXHVjNzA0XHVjZTU4XHViMjk0LCBcdWMyYjlcdWM2ZDBcdWM3NzRcdWFjMDAgXHVjYzk4XHVjNzRjIFx1YWNiZFx1YzdjMVx1ZDU2MCBcdWI1NGMgXHVjMGJjXHVjNzQ0IFx1ZDQ1Y1x1YzgwMVx1Yzc1OCBcdWJjODhcdWQ2MzhcdWI5N2MgXHViNzNiXHVkNTVjXHViMmU0LiBcdWI5Y2NcdWM1N2RcdWM1ZDAgXHVjZDVjXHVjODAxXHVjNzU4IFx1YzcwNFx1Y2U1OFx1YWMwMCBcdWM1ZWNcdWI3ZWMgXHVhY2YzXHVjNzc0XHViNzdjXHViYTc0LCBcdWFkZjggXHVjOTExIFx1YWMwMFx1YzdhNSBcdWJjODhcdWQ2MzhcdWFjMDAgXHViMTkyXHVjNzQwIFx1YzcwNFx1Y2U1OFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWJhNzQgXHViNDFjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5cdWMyYjlcdWM2ZDBcdWM3NzRcdWM3NTggXHVjMmU0XHViODI1IFx1YjRmMVx1YWUwOVx1Yzc0MCA3XHVjNzc0XHViMmU0LiAxXHViYzg4IFx1ZDQ1Y1x1YzgwMVx1YzVkMFx1YzExYyBcdWMyZGNcdWM3OTFcdWQ1NjAgXHVhY2JkXHVjNmIwIFx1YzJiOVx1YzZkMFx1Yzc3NFx1YjI5NCA0XHViYzg4IFx1ZDQ1Y1x1YzgwMVx1YzczY1x1Yjg1YyBcdWFjMDQgXHVkNmM0IFx1YjA1ZFx1YWU0Y1x1YzljMCBcdWQ1NzRcdWIyZjkgXHVkNDVjXHVjODAxXHVjNWQwIFx1YmEzOFx1YmIzNFx1Yjk3OFx1YjJlNC4gMlx1YmM4OCBcdWQ0NWNcdWM4MDFcdWM3NzRcdWIwOTggNFx1YmM4OCBcdWQ0NWNcdWM4MDFcdWM1ZDBcdWMxMWMgXHVjMmRjXHVjNzkxXHVkNTYwIFx1YWNiZFx1YzZiMCBcdWMyYjlcdWM2ZDBcdWM3NzRcdWIyOTQgXHViMDVkXHVhZTRjXHVjOWMwIFx1ZDU3NFx1YjJmOSBcdWQ0NWNcdWM4MDFcdWM1ZDAgXHViYTM4XHViYjM0XHViOTc4XHViMmU0LiAzXHViYzg4IFx1ZDQ1Y1x1YzgwMVx1YzVkMFx1YzExYyBcdWMyZGNcdWM3OTFcdWQ1NjAgXHVhY2JkXHVjNmIwIFx1YzJiOVx1YzZkMFx1Yzc3NFx1YjI5NCBcdWMyZTRcdWI4MjUgXHViNGYxXHVhZTA5XHVjNzc0IDhcdWM3NzggXHVhZDgxXHVjMjE4XHViOTdjIFx1Yzc3NFx1YWUzMFx1YWNlMCAyXHViYzg4IFx1ZDQ1Y1x1YzgwMVx1YzVkMCBcdWIwNWRcdWFlNGNcdWM5YzAgXHViYTM4XHViYjM0XHViOTc4XHViMmU0LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIiwibGltaXQiOiI8dWw+XHJcblx0PGxpPjEgJmxlOyZuYnNwO04gJmxlOyZuYnNwOzIwMDAwMDxcL2xpPlxyXG5cdDxsaT4yJnRpbWVzO04gJmxlOyBSICZsZTsgMSwwMDAsMDAwLDAwMDxcL2xpPlxyXG48XC91bD5cclxuIn0seyJwcm9ibGVtX2lkIjoiNTQ2MCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkFyY2hlcnkiLCJkZXNjcmlwdGlvbiI6IjxwPkFuIGFyY2hlcnkgdG91cm5hbWVudCBpcyBoZWxkIGFjY29yZGluZyB0byB0aGUgZm9sbG93aW5nIHJ1bGVzLiBUaGVyZSBhcmUgTiB0YXJnZXRzIGFycmFuZ2VkIGluIGEgbGluZSBhbmQgbnVtYmVyZWQgZnJvbSAxIHRvIE4gaW5jbHVzaXZlIGFjY29yZGluZyB0byB0aGVpciBwbGFjZSBvbiB0aGUgbGluZSAodGhlIGxlZnRtb3N0IHRhcmdldCBiZWluZyB0YXJnZXQgMSwgYW5kIHRoZSByaWdodG1vc3QgdGFyZ2V0IGJlaW5nIHRhcmdldCBOKS4gVGhlcmUgYXJlIGFsc28gMipOIGFyY2hlcnMuIEF0IGFueSB0aW1lIGR1cmluZyB0aGUgdG91cm5hbWVudCwgdGhlcmUgYXJlIHR3byBhcmNoZXJzIG9uIGVhY2ggdGFyZ2V0LiBFdmVyeSByb3VuZCBvZiB0aGUgdG91cm5hbWVudCBnb2VzIGFjY29yZGluZyB0byB0aGUgZm9sbG93aW5nIHByb2NlZHVyZTo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5UaGUgdHdvIGFyY2hlcnMgb24gZWFjaCB0YXJnZXQgY29tcGV0ZSB3aXRoIGVhY2ggb3RoZXIgYW5kIGRldGVybWluZSBhIHdpbm5lciBhbmQgYSBsb3NlciBiZXR3ZWVuIHRoZW0uIFRoZW4gYWxsIGFyY2hlcnMgYXJlIHJlYXJyYW5nZWQgYXMgZm9sbG93czpcclxuXHQ8dWw+XHJcblx0XHQ8bGk+VGhlIHdpbm5lcnMgb24gdGFyZ2V0cyAyIHRvIE4gaW5jbHVzaXZlIG1vdmUgdG8gdGhlIHRhcmdldCBvbiB0aGVpciBsZWZ0IChpLmUuLCB0YXJnZXRzIDEgdG8gTiAtIDEgcmVzcGVjdGl2ZWx5KS48XC9saT5cclxuXHRcdDxsaT5UaGUgbG9zZXJzIG9uIHRhcmdldHMgMiB0byBOIGluY2x1c2l2ZSwgYXMgd2VsbCBhcyB0aGUgd2lubmVyIG9uIHRhcmdldCAxLCByZW1haW4gb24gdGhlIHNhbWUgdGFyZ2V0LjxcL2xpPlxyXG5cdFx0PGxpPlRoZSBsb3NlciBvbiB0YXJnZXQgMSBtb3ZlcyB0byB0YXJnZXQgTi48XC9saT5cclxuXHQ8XC91bD5cclxuXHQ8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5UaGUgdG91cm5hbWVudCBjb250aW51ZXMgZm9yIFIgcm91bmRzLCB3aXRoIHRoZSBudW1iZXIgb2Ygcm91bmRzIGJlaW5nIGF0IGxlYXN0IGFzIG1hbnkgYXMgdGhlIG51bWJlciBvZiBhcmNoZXJzIChpLmUuLCBSICZnZTsgMipOKS48XC9wPlxyXG5cclxuPHA+WW91IGFyZSB0aGUgb25seSBhcmNoZXIgdG8gYXJyaXZlIGZvciB0aGUgdG91cm5hbWVudCBleGFjdGx5IG9uIHRpbWUuIEFsbCBvdGhlciAyKk4gLSAxIGFyY2hlcnMgaGF2ZSBhcnJpdmVkIGVhcmx5IGFuZCBhcmUgYWxyZWFkeSBzdGFuZGluZyBpbiBhIGxpbmUuIFdoYXQgeW91IGhhdmUgdG8gZG8gbm93IGlzIHRvIGluc2VydCB5b3Vyc2VsZiBzb21ld2hlcmUgaW50byB0aGUgbGluZSBhbW9uZ3N0IHRoZW0uIFlvdSBrbm93IHRoYXQgYWZ0ZXIgeW91IHRha2UgeW91ciBwb3NpdGlvbiwgdGhlIHR3byBsZWZ0bW9zdCBhcmNoZXJzIGluIHRoZSBsaW5lIHdpbGwgc3RhcnQgdGhlIHRvdXJuYW1lbnQgb24gdGFyZ2V0IDEsIHRoZSBuZXh0IHR3byB3aWxsIHN0YXJ0IG9uIHRhcmdldCAyIGFuZCBzbyBvbiwgd2l0aCB0aGUgdHdvIHJpZ2h0bW9zdCBhcmNoZXJzIHN0YXJ0aW5nIG9uIHRhcmdldCBOLjxcL3A+XHJcblxyXG48cD5BbGwgdGhlIDIqTiBhcmNoZXJzIGluIHRoZSB0b3VybmFtZW50IChpbmNsdWRpbmcgeW91cnNlbGYpIGFyZSByYW5rZWQgYnkgc2tpbGwsIHdoZXJlIGEgc21hbGxlciByYW5rIGNvcnJlc3BvbmRzIHRvIGJldHRlciBza2lsbC4gTm8gdHdvIGFyY2hlcnMgaGF2ZSB0aGUgc2FtZSByYW5rLiBBbHNvLCB3aGVuZXZlciB0d28gYXJjaGVycyBjb21wZXRlLCB0aGUgb25lIHdpdGggdGhlIHNtYWxsZXIgcmFuayB3aWxsIGFsd2F5cyB3aW4uPFwvcD5cclxuXHJcbjxwPktub3dpbmcgaG93IHNraWxsZWQgZWFjaCBvZiB5b3VyIGNvbXBldGl0b3JzIGlzLCB5b3Ugd2FudCB0byBpbnNlcnQgeW91cnNlbGYgaW4gc3VjaCBhIHdheSBhcyB0byBlbnN1cmUgdGhhdCB5b3Ugd2lsbCBmaW5pc2ggdGhlIHRvdXJuYW1lbnQgb24gYSB0YXJnZXQgd2l0aCBhcyBzbWFsbCBhIG51bWJlciBhcyBwb3NzaWJsZS4gSWYgdGhlcmUgYXJlIG11bHRpcGxlIHdheXMgdG8gZG8gdGhpcywgeW91IHByZWZlciB0aGUgb25lIHRoYXQgc3RhcnRzIGF0IGEgdGFyZ2V0IHdpdGggYXMgbGFyZ2UgYSBudW1iZXIgYXMgcG9zc2libGUuJm5ic3A7PFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB0aGF0LCBnaXZlbiB0aGUgcmFua3Mgb2YgYWxsIGFyY2hlcnMsIGluY2x1ZGluZyB5b3Vyc2VsZiwgYXMgd2VsbCBhcyB5b3VyIGNvbXBldGl0b3JzJnJzcXVvOyBhcnJhbmdlbWVudCBvbiB0aGUgbGluZSwgZGV0ZXJtaW5lcyBvbiB3aGljaCB0YXJnZXQgeW91IHNob3VsZCBzdGFydCB0aGUgdG91cm5hbWVudCwgc28gdGhhdCB5b3UgY2FuIGFjaGlldmUgeW91ciBnb2FscyBhcyBkZWZpbmVkIGFib3ZlLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+WW91ciBwcm9ncmFtIG11c3QgcmVhZCBmcm9tIHN0YW5kYXJkIGlucHV0IHRoZSBmb2xsb3dpbmcgZGF0YTo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5UaGUgZmlyc3QgbGluZSBjb250YWlucyB0aGUgaW50ZWdlcnMgTiBhbmQgUiwgc2VwYXJhdGVkIGJ5IGEgc3BhY2UuPFwvbGk+XHJcblx0PGxpPlRoZSBuZXh0IDIqTiBsaW5lcyBsaXN0IHRoZSByYW5rcyBvZiB0aGUgYXJjaGVycy4gVGhlIGZpcnN0IG9mIHRoZXNlIGxpbmVzIGNvbnRhaW5zIHlvdXIgcmFuay4gVGhlIHJlc3Qgb2YgdGhlc2UgbGluZXMgY29udGFpbiB0aGUgcmFua3Mgb2YgdGhlIG90aGVyIGFyY2hlcnMsIG9uZSBhcmNoZXIgcGVyIGxpbmUsIGluIHRoZSBvcmRlciBpbiB3aGljaCB0aGV5IGhhdmUgYXJyYW5nZWQgdGhlbXNlbHZlcyAoZnJvbSBsZWZ0IHRvIHJpZ2h0KS4gRWFjaCBvZiB0aGVzZSAyKk4gbGluZXMgY29udGFpbnMgYSBzaW5nbGUgaW50ZWdlciBiZXR3ZWVuIDEgYW5kIDIqTiBpbmNsdXNpdmUuIEEgcmFuayBvZiAxIGlzIHRoZSBiZXN0IGFuZCBhIHJhbmsgb2YgMipOIGlzIHRoZSB3b3JzdC4gTm8gdHdvIGFyY2hlcnMgaGF2ZSB0aGUgc2FtZSByYW5rLjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+MSAmbGU7IE4gJmxlOyAyMDAsMDAwIFRoZSBudW1iZXIgb2YgdGFyZ2V0czsgYWxzbyBlcXVhbCB0byBoYWxmIHRoZSBudW1iZXIgb2YgYXJjaGVyczxcL2xpPlxyXG5cdDxsaT4yKk4gJmxlOyBSICZsZTsgMSwwMDAsMDAwLDAwMCBUaGUgbnVtYmVyIG9mIHRvdXJuYW1lbnQgcm91bmRzPFwvbGk+XHJcblx0PGxpPjEgJmxlOyBTayAmbGU7IDIqTiBUaGUgcmFuayBvZiBhcmNoZXIgazxcL2xpPlxyXG48XC91bD5cclxuIiwib3V0cHV0IjoiPHA+WW91ciBwcm9ncmFtIG11c3Qgd3JpdGUgdG8gc3RhbmRhcmQgb3V0cHV0IGEgc2luZ2xlIGxpbmUgY29udGFpbmluZyBhIHNpbmdsZSBpbnRlZ2VyIGJldHdlZW4gMSBhbmQgTiBpbmNsdXNpdmU6IHRoZSBudW1iZXIgb2YgdGhlIHRhcmdldCBvbiB3aGljaCB5b3Ugd2lsbCBzdGFydCB0aGUgdG91cm5hbWVudC4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiPHA+U2FtcGxlIDE8XC9wPlxyXG5cclxuPHA+WW91IGFyZSB0aGUgc2Vjb25kIHdvcnN0IGFyY2hlci4gSWYgeW91IHN0YXJ0IG9uIHRhcmdldCAxLCB5b3Ugd2lsbCB0aGVuIGdvIHRvIHRhcmdldCA0IGFuZCBzdGF5IHRoZXJlIHVudGlsIHRoZSBlbmQuIElmIHlvdSBzdGFydCBvbiB0YXJnZXQgMiBvciA0LCB5b3Ugd2lsbCBqdXN0IHN0YXkgdGhlcmUgZm9yIHRoZSB3aG9sZSB0b3VybmFtZW50LiBJZiB5b3Ugc3RhcnQgb24gdGFyZ2V0IDMsIHlvdSB3aWxsIGJlYXQgdGhlIHdvcnN0IGFyY2hlciBhbmQgdGhlbiBtb3ZlIHRvIHRhcmdldCAyIGFuZCBzdGF5IHRoZXJlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5TYW1wbGUgMjxcL3A+XHJcblxyXG48cD5Zb3UgYXJlIHRoZSBzZWNvbmQgYmVzdCBhcmNoZXIuIFRoZSBiZXN0IG9uZSBpcyBhbHJlYWR5IG9uIHRhcmdldCAxIGFuZCB3aWxsIHN0YXkgdGhlcmUgZm9yIHRoZSB3aG9sZSBkdXJhdGlvbiBvZiB0aGUgdG91cm5hbWVudC4gVGh1cywgbm8gbWF0dGVyIHdoZXJlIHlvdSBzdGFydCwgeW91IHdpbGwgYWx3YXlzIG1vdmUgZnJvbSB5b3VyIHRhcmdldCwgZ29pbmcgdGhyb3VnaCBhbGwgdGFyZ2V0cyBmcm9tIDQgdG8gMSBvdmVyIGFuZCBvdmVyIGFnYWluLiBJbiBvcmRlciBmb3IgeW91IHRvIGVuZCBvbiB0YXJnZXQgMSBhZnRlciA5IHRyYW5zaXRpb25zLCB5b3UgaGF2ZSB0byBzdGFydCBvbiB0YXJnZXQgMi4mbmJzcDs8XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

Olympiad > International Olympiad in Informatics > IOI 2009 > Day 1 1번

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