시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB222382517.857%

문제

1행 m열의 직사각형 체스판 위에서 진행하는 게임을 가정해 보자. 체스판의 각 칸에는 1부터 m까지 번호가 매겨져 있다. n개의 폰 (pawn)이 하나씩의 칸을 차지한 채로 체스판 위에 놓여 있으며, m번 칸은 비어 있다. 두 명의 플레이어가 게임을 한다. 각 플레이어는 자기 차례가 오면 i번 칸에 놓인 폰을 집어서 j번 칸으로 이동시킬 수 있다. 이때, j는 비어있는 칸의 번호 중 최솟값인데, 다만 i보다는 커야 한다. 게임의 승자는 마지막 칸인 m번 칸에 폰을 집어넣는 사람이다.

예를 들어, m=7인 그림의 상황에서 차례가 된 플레이어는 2번 칸의 폰을 4번 칸으로 옮길 수 있고, 3번 칸의 폰을 4번 칸으로 옮길 수도 있으며, 6번 칸의 폰을 7번 칸으로 옮겨 게임을 이길 수도 있다.

어떤 플레이어의 수가 ‘필승수'라고 하는 것은, 그 수를 둔 후엔 상대편이 어떤 수를 두더라도 반드시 이길 수 있는 경우를 말한다. 체스판의 현재 상황이 주어졌을 때, 이번에 차례를 맞은 플레이어가 둘 수 있는 필승수의 가짓수를 계산하는 프로그램을 작성하라.

입력

첫째 줄에 두 양의 정수 m과 n이 주어진다. (2 ≤ m ≤ 109, 1 ≤ n ≤ 106, n<m) 둘째 줄에는 n개의 양의 정수가 오름차순으로 주어지는데, 이는 각각 현재 폰이 놓여 있는 칸의 번호를 나타낸다.

출력

첫째 줄에 이번에 차례를 맞은 플레이어가 둘 수 있는 필승수의 가짓수를 출력한다.

예제 입력 1

5 2
1 3

예제 출력 1

1

예제 입력 2

5 2
2 3

예제 출력 2

0
W3sicHJvYmxlbV9pZCI6IjE4NDIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjOGNcdWM3ODRcdWQ1NThcdWFlMzAiLCJkZXNjcmlwdGlvbiI6IjxwPjFcdWQ1ODkgbVx1YzVmNFx1Yzc1OCBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTUgXHVjY2I0XHVjMmE0XHVkMzEwIFx1YzcwNFx1YzVkMFx1YzExYyBcdWM5YzRcdWQ1ODlcdWQ1NThcdWIyOTQgXHVhYzhjXHVjNzg0XHVjNzQ0IFx1YWMwMFx1YzgxNVx1ZDU3NCBcdWJjZjRcdWM3OTAuIFx1Y2NiNFx1YzJhNFx1ZDMxMFx1Yzc1OCBcdWFjMDEgXHVjZTc4XHVjNWQwXHViMjk0IDFcdWJkODBcdWQxMzAgbVx1YWU0Y1x1YzljMCBcdWJjODhcdWQ2MzhcdWFjMDAgXHViOWU0XHVhY2E4XHVjODM4IFx1Yzc4OFx1YjJlNC4gblx1YWMxY1x1Yzc1OCBcdWQzZjAgKHBhd24pXHVjNzc0IFx1ZDU1OFx1YjA5OFx1YzUyOVx1Yzc1OCBcdWNlNzhcdWM3NDQgXHVjYzI4XHVjOWMwXHVkNTVjIFx1Y2M0NFx1Yjg1YyBcdWNjYjRcdWMyYTRcdWQzMTAgXHVjNzA0XHVjNWQwIFx1YjE5M1x1YzVlYyBcdWM3ODhcdWM3M2NcdWJhNzAsIG1cdWJjODggXHVjZTc4XHVjNzQwIFx1YmU0NFx1YzViNCBcdWM3ODhcdWIyZTQuIFx1YjQ1MCBcdWJhODVcdWM3NTggXHVkNTBjXHViODA4XHVjNzc0XHVjNWI0XHVhYzAwIFx1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWQ1NWNcdWIyZTQuIFx1YWMwMSBcdWQ1MGNcdWI4MDhcdWM3NzRcdWM1YjRcdWIyOTQgXHVjNzkwXHVhZTMwIFx1Y2MyOFx1Yjg0MFx1YWMwMCBcdWM2MjRcdWJhNzQgaVx1YmM4OCBcdWNlNzhcdWM1ZDAgXHViMTkzXHVjNzc4IFx1ZDNmMFx1Yzc0NCBcdWM5ZDFcdWM1YjRcdWMxMWMgalx1YmM4OCBcdWNlNzhcdWM3M2NcdWI4NWMgXHVjNzc0XHViM2Q5XHVjMmRjXHVkMGFjIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1Yzc3NFx1YjU0Yywgalx1YjI5NCBcdWJlNDRcdWM1YjRcdWM3ODhcdWIyOTQgXHVjZTc4XHVjNzU4IFx1YmM4OFx1ZDYzOCBcdWM5MTEgXHVjZDVjXHVjMTlmXHVhYzEyXHVjNzc4XHViMzcwLCBcdWIyZTRcdWI5Y2MgaVx1YmNmNFx1YjJlNFx1YjI5NCBcdWNlZTRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWFjOGNcdWM3ODRcdWM3NTggXHVjMmI5XHVjNzkwXHViMjk0IFx1YjljOFx1YzljMFx1YjljOSBcdWNlNzhcdWM3NzggbVx1YmM4OCBcdWNlNzhcdWM1ZDAgXHVkM2YwXHVjNzQ0IFx1YzlkMVx1YzViNFx1YjEyM1x1YjI5NCBcdWMwYWNcdWI3OGNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgaGVpZ2h0PVwiNzRcIiBzcmM9XCJcL0p1ZGdlT25saW5lXC91cGxvYWRcLzIwMTAwNlwvU2NyZWVuIHNob3QgMjAxMC0wNi0xMSBhdCA4XzE2XzQ0IFBNLnBuZ1wiIHdpZHRoPVwiMzQ0XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIG09N1x1Yzc3OCBcdWFkZjhcdWI5YmNcdWM3NTggXHVjMGMxXHVkNjY5XHVjNWQwXHVjMTFjIFx1Y2MyOFx1Yjg0MFx1YWMwMCBcdWI0MWMgXHVkNTBjXHViODA4XHVjNzc0XHVjNWI0XHViMjk0IDJcdWJjODggXHVjZTc4XHVjNzU4IFx1ZDNmMFx1Yzc0NCA0XHViYzg4IFx1Y2U3OFx1YzczY1x1Yjg1YyBcdWM2MmVcdWFlMzggXHVjMjE4IFx1Yzc4OFx1YWNlMCwgM1x1YmM4OCBcdWNlNzhcdWM3NTggXHVkM2YwXHVjNzQ0IDRcdWJjODggXHVjZTc4XHVjNzNjXHViODVjIFx1YzYyZVx1YWUzOCBcdWMyMThcdWIzYzQgXHVjNzg4XHVjNzNjXHViYTcwLCA2XHViYzg4IFx1Y2U3OFx1Yzc1OCBcdWQzZjBcdWM3NDQgN1x1YmM4OCBcdWNlNzhcdWM3M2NcdWI4NWMgXHVjNjJlXHVhY2E4IFx1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWM3NzRcdWFlMzggXHVjMjE4XHViM2M0IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNWI0XHViNWE0IFx1ZDUwY1x1YjgwOFx1Yzc3NFx1YzViNFx1Yzc1OCBcdWMyMThcdWFjMDAgJmxzcXVvO1x1ZDU0NFx1YzJiOVx1YzIxOCYjMzk7XHViNzdjXHVhY2UwIFx1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NDAsIFx1YWRmOCBcdWMyMThcdWI5N2MgXHViNDU0IFx1ZDZjNFx1YzVkNCBcdWMwYzFcdWIzMDBcdWQzYjhcdWM3NzQgXHVjNWI0XHViNWE0IFx1YzIxOFx1Yjk3YyBcdWI0NTBcdWIzNTRcdWI3N2NcdWIzYzQgXHViYzE4XHViNGRjXHVjMmRjIFx1Yzc3NFx1YWUzOCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWNiZFx1YzZiMFx1Yjk3YyBcdWI5ZDBcdWQ1NWNcdWIyZTQuIFx1Y2NiNFx1YzJhNFx1ZDMxMFx1Yzc1OCBcdWQ2MDRcdWM3YWMgXHVjMGMxXHVkNjY5XHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1Yzc3NFx1YmM4OFx1YzVkMCBcdWNjMjhcdWI4NDBcdWI5N2MgXHViOWRlXHVjNzQwIFx1ZDUwY1x1YjgwOFx1Yzc3NFx1YzViNFx1YWMwMCBcdWI0NTggXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWQ1NDRcdWMyYjlcdWMyMThcdWM3NTggXHVhYzAwXHVjOWQzXHVjMjE4XHViOTdjIFx1YWNjNFx1YzBiMFx1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHViNzdjLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWI0NTAgXHVjNTkxXHVjNzU4IFx1YzgxNVx1YzIxOCBtXHVhY2ZjIG5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMiAmbGU7IG0gJmxlOyZuYnNwOzEwPHN1cD45PFwvc3VwPiwgMSAmbGU7IG4gJmxlOyAxMDxzdXA+NjxcL3N1cD4sIG5cdWZmMWNtKSBcdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IG5cdWFjMWNcdWM3NTggXHVjNTkxXHVjNzU4IFx1YzgxNVx1YzIxOFx1YWMwMCBcdWM2MjRcdWI5ODRcdWNjMjhcdWMyMWNcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0XHViMzcwLCBcdWM3NzRcdWIyOTQgXHVhYzAxXHVhYzAxIFx1ZDYwNFx1YzdhYyBcdWQzZjBcdWM3NzQgXHViMTkzXHVjNWVjIFx1Yzc4OFx1YjI5NCBcdWNlNzhcdWM3NTggXHViYzg4XHVkNjM4XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiOFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1Yzc3NFx1YmM4OFx1YzVkMCBcdWNjMjhcdWI4NDBcdWI5N2MgXHViOWRlXHVjNzQwIFx1ZDUwY1x1YjgwOFx1Yzc3NFx1YzViNFx1YWMwMCBcdWI0NTggXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWQ1NDRcdWMyYjlcdWMyMThcdWM3NTggXHVhYzAwXHVjOWQzXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIxODQyIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiR2FtZSIsImRlc2NyaXB0aW9uIjoiPHA+TGV0IHVzIGNvbnNpZGVyIGEgZ2FtZSBvbiBhIHJlY3Rhbmd1bGFyIGJvYXJkIG0gJnRpbWVzOyAxIGNvbnNpc3Rpbmcgb2YgbSBlbGVtZW50YXJ5IHNxdWFyZXMgbnVtYmVyZWQgc3VjY2Vzc2l2ZWx5IGZyb20gMSB0byBtLiBUaGVyZSBhcmUgbiBwYXducyBvbiB0aGUgYm9hcmQsIGVhY2ggb24gYSBkaXN0aW5jdCBzcXVhcmUuIE5vbmUgb2YgdGhlbSBvY2N1cGllcyB0aGUgc3F1YXJlIHdpdGggbnVtYmVyIG0uIEVhY2ggc2luZ2xlIG1vdmUgaW4gdGhlIGlzIHRoZSBmb2xsb3dpbmcgYWN0aW9uOiB0aGUgbW92aW5nIHBsYXllciBwaWNrcyBhIHBhd24gZnJvbSBhbnkgb2NjdXBpZWQgc3F1YXJlIGNob3NlbiBhdCB3aWxsIGFuZCBwbGFjZXMgaXQgb24gdGhlIGZpcnN0IHVub2NjdXBpZWQgc3F1YXJlIHdpdGggYSBsYXJnZXIgbnVtYmVyLiBUaGUgdHdvIHBsYXllcnMgbWFrZSBtb3ZlcyBpbiB0dXJuLiBUaGUgb25lIHdobyBwdXRzIGEgcGF3biBvbiB0aGUgbGFzdCBzcXVhcmUsIGkuZS4gdGhlIHNxdWFyZSB3aXRoIGEgbnVtYmVyIG0sIHdpbnMuPFwvcD5cclxuXHJcbjxwPkluIHRoZSBjYXNlIHByZXNlbnRlZCBpbiB0aGUgZmlndXJlIChtID0gNyksIGEgcGxheWVyIGlzIGFsbG93ZWQgdG8gbW92ZSBhIHBhd24gZnJvbSBzcXVhcmUgbm8uIDIgdG8gNCwgZnJvbSBzcXVhcmUgbm8uIDMgdG8gNCBvciBmcm9tIHNxdWFyZSBuby4gNiB0byA3LiBUaGUgbGF0dGVyIGVuZHMgdGhlIGdhbWUuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvZ3JhemFkLmdpZlwiIHN0eWxlPVwiaGVpZ2h0Ojg1cHg7IHdpZHRoOjQwMnB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPldlIHNheSBhIHBsYXllciYjMzk7cyBtb3ZlIGlzIHdpbm5pbmcgaWYgYWZ0ZXIgbWFraW5nIGl0IGhlIGNhbiB3aW4gdGhlIGdhbWUsIG5vIG1hdHRlciB3aGF0IG1vdmVzIGhpcyBvcHBvbmVudCBtYWtlcy48XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtbWUgdGhhdDo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5yZWFkcyB0aGUgc2l6ZSBvZiBhIGJvYXJkIGFuZCB0aGUgaW5pdGlhbCBzZXR1cCBvZiBwYXducyBmcm9tIHRoZSBzdGFuZGFyZCBpbnB1dCw8XC9saT5cclxuXHQ8bGk+ZGV0ZXJtaW5lcyB0aGUgbnVtYmVyIG9mIGRpc3RpbmN0IHdpbm5pbmcgbW92ZXMgdGhlIHN0YXJ0aW5nIHBsYXllciBtYXkgY2hvb3NlIGluIHRoZSBnaXZlbiBpbml0aWFsIHNpdHVhdGlvbiw8XC9saT5cclxuXHQ8bGk+d3JpdGVzIHRoZSByZXN1bHQgdG8gdGhlIHN0YW5kYXJkIG91dHB1dC48XC9saT5cclxuPFwvdWw+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgdGhlIGlucHV0IGNvbnRhaW5zIHR3byBpbnRlZ2VycyBtIGFuZCBuICgyICZsZTsgbSAmbGU7IDEwPHN1cD45PFwvc3VwPiwgMSAmbGU7IG4gJmxlOyAxMDxzdXA+NjxcL3N1cD4sIG4gJmx0OyBtKSBzZXBhcmF0ZWQgYnkgYSBzaW5nbGUgc3BhY2UuIFRoZSBzZWNvbmQgbGluZSBjb250YWlucyAmbmJzcDtpbmNyZWFzaW5nIG51bWJlcnMgLSB0aGVzZSBhcmUgdGhlIG51bWJlcnMgb2Ygc3F1YXJlcyB0aGUgcGF3bnMgYXJlIHNldCBvbi4gTnVtYmVycyBpbiB0aGUgbGluZSBhcmUgc2VwYXJhdGVkIGJ5IHNpbmdsZSBzcGFjZXMuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBmaXJzdCBhbmQgb25seSBvdXRwdXQgbGluZSBzaG91bGQgY29udGFpbiB0aGUgbnVtYmVyIG9mIGRpc3RpbmN0IHdpbm5pbmcgbW92ZXMgcG9zc2libGUgZm9yIHRoZSBzdGFydGluZyBwbGF5ZXIgaW4gdGhlIGdpdmVuIGluaXRpYWwgc2l0dWF0aW9uLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

Olympiad > Polish Olympiad in Informatics > POI 2003/2004 > Stage 1 1번