시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 72 32 31 53.448%

문제

원 모양으로 나열된 N개의 필드를 가진 게임판이 있다. 각 필드는 1~N까지 시계방향으로 숫자가 매겨져 있다. 몇개의 필드에는 장애물이 놓여져 있다.

아람이는 1에서 게임을 시작한다. Z번째 필드에 도착하는 것이 이 게임의 목표이다. 도착점은 K만큼씩 시계방향으로 이동해 도달해야 한다. 도착점으로 가는 길에 장애물이 있는 필드를 밟아서는 안 된다.

예를들어 N=13, K=3 그리고 Z=9라고 했을 때 아람이는 1,4,7,10,13,3,6 그리고 9 의 필드를 지나게 된다. 도착점으로 가는 경로 중 장애물이 있는 필드가 하나라도 있으면 안 된다.

게임판의 정보가 주어졌을 때 도착점에 도착할 수 있는 가장 작은 K를 찾는 프로그램을 작성하시오.

입력

입력의 첫째 줄에는 N(2 ≤ N ≤ 1000), Z(2 ≤ Z), M(0 ≤ M ≤ N-2) 이 주어진다.

N은 필드의 수이고 Z는 도착해야하는 필드의 번호를 의미한다.

다음 줄에 M개의 서로 다른 정수가 주어진다. 이 정수는 장애물이 있는 필드의 번호를 나타낸다.

1번과 Z번째 필드에는 장애물이 놓이지 않는다.

출력

출력의 첫 번째 줄에 위에서 정의되어진 K를 출력한다.

예제 입력 1

7 4 1
6

예제 출력 1

1

예제 입력 2

9 7 2
2 3

예제 출력 2

3

예제 입력 3

7 6 2
2 4

예제 출력 3

5
W3sicHJvYmxlbV9pZCI6IjMyNTgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWNlZjRcdWQzZWNcdWQyYjgiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzZkMCBcdWJhYThcdWM1OTFcdWM3M2NcdWI4NWMgXHViMDk4XHVjNWY0XHViNDFjIE5cdWFjMWNcdWM3NTggXHVkNTQ0XHViNGRjXHViOTdjIFx1YWMwMFx1YzljNCBcdWFjOGNcdWM3ODRcdWQzMTBcdWM3NzQgXHVjNzg4XHViMmU0LiBcdWFjMDEgXHVkNTQ0XHViNGRjXHViMjk0IDF+Tlx1YWU0Y1x1YzljMCBcdWMyZGNcdWFjYzRcdWJjMjlcdWQ1YTVcdWM3M2NcdWI4NWMgXHVjMjJiXHVjNzkwXHVhYzAwIFx1YjllNFx1YWNhOFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YmE4N1x1YWMxY1x1Yzc1OCBcdWQ1NDRcdWI0ZGNcdWM1ZDBcdWIyOTQgXHVjN2E1XHVjNTYwXHViYjNjXHVjNzc0IFx1YjE5M1x1YzVlY1x1YzgzOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzU0NFx1Yjc4Y1x1Yzc3NFx1YjI5NCAxXHVjNWQwXHVjMTFjIFx1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWMyZGNcdWM3OTFcdWQ1NWNcdWIyZTQuIFpcdWJjODhcdWM5ZjggXHVkNTQ0XHViNGRjXHVjNWQwIFx1YjNjNFx1Y2MyOVx1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NzQgXHVjNzc0IFx1YWM4Y1x1Yzc4NFx1Yzc1OCBcdWJhYTlcdWQ0NWNcdWM3NzRcdWIyZTQuIFx1YjNjNFx1Y2MyOVx1YzgxMFx1Yzc0MCZuYnNwO0tcdWI5Y2NcdWQwN2NcdWM1MjkgXHVjMmRjXHVhY2M0XHViYzI5XHVkNWE1XHVjNzNjXHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU3NCBcdWIzYzRcdWIyZWNcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWIzYzRcdWNjMjlcdWM4MTBcdWM3M2NcdWI4NWMgXHVhYzAwXHViMjk0IFx1YWUzOFx1YzVkMCBcdWM3YTVcdWM1NjBcdWJiM2NcdWM3NzQgXHVjNzg4XHViMjk0IFx1ZDU0NFx1YjRkY1x1Yjk3YyBcdWJjMWZcdWM1NDRcdWMxMWNcdWIyOTQgXHVjNTQ4IFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNjA4XHViOTdjXHViNGU0XHVjNWI0IE49MTMsIEs9MyBcdWFkZjhcdWI5YWNcdWFjZTAgWj05XHViNzdjXHVhY2UwIFx1ZDU4OFx1Yzc0NCBcdWI1NGMgXHVjNTQ0XHViNzhjXHVjNzc0XHViMjk0IDEsNCw3LDEwLDEzLDMsNiBcdWFkZjhcdWI5YWNcdWFjZTAgOSBcdWM3NTggXHVkNTQ0XHViNGRjXHViOTdjIFx1YzljMFx1YjA5OFx1YWM4YyBcdWI0MWNcdWIyZTQuIFx1YjNjNFx1Y2MyOVx1YzgxMFx1YzczY1x1Yjg1YyBcdWFjMDBcdWIyOTQgXHVhY2JkXHViODVjIFx1YzkxMSZuYnNwO1x1YzdhNVx1YzU2MFx1YmIzY1x1Yzc3NCBcdWM3ODhcdWIyOTQgXHVkNTQ0XHViNGRjXHVhYzAwIFx1ZDU1OFx1YjA5OFx1Yjc3Y1x1YjNjNCBcdWM3ODhcdWM3M2NcdWJhNzQgXHVjNTQ4IFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzhjXHVjNzg0XHVkMzEwXHVjNzU4IFx1YzgxNVx1YmNmNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjIFx1YjNjNFx1Y2MyOVx1YzgxMFx1YzVkMCBcdWIzYzRcdWNjMjlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFjMDBcdWM3YTUgXHVjNzkxXHVjNzQwIEtcdWI5N2MgXHVjYzNlXHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NTggXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBOKDIgJmxlOyBOICZsZTsgMTAwMCksIFooMiAmbGU7IFopLCBNKDAgJmxlOyBNICZsZTsgTi0yKSBcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5OXHVjNzQwIFx1ZDU0NFx1YjRkY1x1Yzc1OCBcdWMyMThcdWM3NzRcdWFjZTAgWlx1YjI5NCBcdWIzYzRcdWNjMjlcdWQ1NzRcdWM1N2NcdWQ1NThcdWIyOTQgXHVkNTQ0XHViNGRjXHVjNzU4IFx1YmM4OFx1ZDYzOFx1Yjk3YyBcdWM3NThcdWJiZjhcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBcdWM5MDRcdWM1ZDAgTVx1YWMxY1x1Yzc1OCBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1YzgxNVx1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NCBcdWM4MTVcdWMyMThcdWIyOTQgXHVjN2E1XHVjNTYwXHViYjNjXHVjNzc0IFx1Yzc4OFx1YjI5NCBcdWQ1NDRcdWI0ZGNcdWM3NTggXHViYzg4XHVkNjM4XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+MVx1YmM4OFx1YWNmYyBaXHViYzg4XHVjOWY4IFx1ZDU0NFx1YjRkY1x1YzVkMFx1YjI5NCBcdWM3YTVcdWM1NjBcdWJiM2NcdWM3NzQgXHViMTkzXHVjNzc0XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNkOWNcdWI4MjVcdWM3NTggXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjNzA0XHVjNWQwXHVjMTFjIFx1YzgxNVx1Yzc1OFx1YjQxOFx1YzViNFx1YzljNCBLXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzMjU4IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQ09NRk9SVCIsImRlc2NyaXB0aW9uIjoiPHA+QSBnYW1lLWJvYXJkIGNvbnNpc3RzIG9mIE4gZmllbGRzIHBsYWNlZCBhcm91bmQgYSBjaXJjbGUuIEZpZWxkcyBhcmUgc3VjY2Vzc2l2ZWx5IG51bWJlcmVkIGZyb20xIHRvIE4gY2xvY2t3aXNlLiBPbiBzb21lIG9mIHRoZSBmaWVsZHMgdGhlcmUgYXJlIG9ic3RhY2xlcy48XC9wPlxyXG5cclxuPHA+UGxheWVyIHN0YXJ0cyBvbiBhIGZpZWxkIG1hcmtlZCB3aXRoIG51bWJlciAxLiBIaXMgZ29hbCBpcyB0byByZWFjaCBhIGdpdmVuIGZpZWxkIG1hcmtlZCB3aXRoIG51bWJlciBaIHVzaW5nIG9ubHkgbW92ZXMgY29uc2lzdGluZyBvZiBjbG9ja3dpc2UganVtcHMgb2YgbGVuZ3RoIEsuIFRoZSBwbGF5ZXImcnNxdW87cyBwYXRoIHNob3VsZCBub3QgY29udGFpbiBhbnkgb2YgdGhlIGZpZWxkcyBoYXZpbmcgYW4gb2JzdGFjbGUuPFwvcD5cclxuXHJcbjxwPkZvciBleGFtcGxlLCBpZiBOPTEzLCBLPTMgYW5kIFo9OSwgdGhlIHBsYXllciBjYW4ganVtcCBhY3Jvc3MgdGhlIGZpZWxkcyAxLCA0LCA3LCAxMCwgMTMsIDMsIDYgYW5kIDksIHJlYWNoaW5nIGhpcyBnb2FsIHVuZGVyIGNvbmRpdGlvbiB0aGF0IG5vbmUgb2YgdGhlc2UgZmllbGRzIGhhcyBhbiBvYnN0YWNsZSBvbiBpdC48XC9wPlxyXG5cclxuPHA+WW91ciB0YXNrIGlzIHRvIHdyaXRlIGEgcHJvZ3JhbSB0aGF0IGZpbmRzIHRoZSBzbWFsbGVzdCBwb3NzaWJsZSBudW1iZXIgSy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPkZpcnN0IGxpbmUgb2YgdGhlIGlucHV0IGZpbGUgY29uc2lzdHMgb2YgaW50ZWdlcnMgTiwgWiBhbmQgTSwgMiAmbGU7IE4gJmxlOyAxMDAwLCAyICZsZTsgWiwgMCAmbGU7IE0gJmxlOyBOLTIuPFwvcD5cclxuXHJcbjxwPk4gcmVwcmVzZW50cyBudW1iZXIgb2YgZmllbGRzIG9uIHRoZSBnYW1lLWJvYXJkIGFuZCBaIGlzIGEgZ2l2ZW4gZ29hbC1maWVsZC48XC9wPlxyXG5cclxuPHA+TmV4dCBsaW5lIGNvbnNpc3RzIG9mIE0gZGlmZmVyZW50IGludGVnZXJzIHRoYXQgcmVwcmVzZW50IG1hcmtzIG9mIGZpZWxkcyBoYXZpbmcgYW4gb2JzdGFjbGUuIEZpZWxkcyBtYXJrZWQgMSBhbmQgWiBkbyBub3QgY29udGFpbiBhbiBvYnN0YWNsZS4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgZmlyc3QgYW5kIG9ubHkgbGluZSBvZiB0aGUgb3V0cHV0IGZpbGUgc2hvdWxkIGNvbnRhaW4gcmVxdWVzdGVkIG51bWJlciBLIGRlZmluZWQgYWJvdmUuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

Olympiad > Croatian Highschool Competitions in Informatics > 2002 > National Competition #1 - Juniors 1번