시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 79 24 11 23.913%

문제

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

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

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

입력

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

출력

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

예제 입력 1

5 2
1 3

예제 출력 1

1
W3sicHJvYmxlbV9pZCI6IjE4NDIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjOGNcdWM3ODRcdWQ1NThcdWFlMzAiLCJkZXNjcmlwdGlvbiI6IjxwPjFcdWQ1ODkgbVx1YzVmNFx1Yzc1OCBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTUgXHVjY2I0XHVjMmE0XHVkMzEwIFx1YzcwNFx1YzVkMFx1YzExYyBcdWM5YzRcdWQ1ODlcdWQ1NThcdWIyOTQgXHVhYzhjXHVjNzg0XHVjNzQ0IFx1YWMwMFx1YzgxNVx1ZDU3NCBcdWJjZjRcdWM3OTAuIFx1Y2NiNFx1YzJhNFx1ZDMxMFx1Yzc1OCBcdWFjMDEgXHVjZTc4XHVjNWQwXHViMjk0IDFcdWJkODBcdWQxMzAgbVx1YWU0Y1x1YzljMCBcdWJjODhcdWQ2MzhcdWFjMDAgXHViOWU0XHVhY2E4XHVjODM4IFx1Yzc4OFx1YjJlNC4gblx1YWMxY1x1Yzc1OCBcdWQzZjAgKHBhd24pXHVjNzc0IFx1ZDU1OFx1YjA5OFx1YzUyOVx1Yzc1OCBcdWNlNzhcdWM3NDQgXHVjYzI4XHVjOWMwXHVkNTVjIFx1Y2M0NFx1Yjg1YyBcdWNjYjRcdWMyYTRcdWQzMTAgXHVjNzA0XHVjNWQwIFx1YjE5M1x1YzVlYyBcdWM3ODhcdWM3M2NcdWJhNzAsIG1cdWJjODggXHVjZTc4XHVjNzQwIFx1YmU0NFx1YzViNCBcdWM3ODhcdWIyZTQuIFx1YjQ1MCBcdWJhODVcdWM3NTggXHVkNTBjXHViODA4XHVjNzc0XHVjNWI0XHVhYzAwIFx1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWQ1NWNcdWIyZTQuIFx1YWMwMSBcdWQ1MGNcdWI4MDhcdWM3NzRcdWM1YjRcdWIyOTQgXHVjNzkwXHVhZTMwIFx1Y2MyOFx1Yjg0MFx1YWMwMCBcdWM2MjRcdWJhNzQgaVx1YmM4OCBcdWNlNzhcdWM1ZDAgXHViMTkzXHVjNzc4IFx1ZDNmMFx1Yzc0NCBcdWM5ZDFcdWM1YjRcdWMxMWMgalx1YmM4OCBcdWNlNzhcdWM3M2NcdWI4NWMgXHVjNzc0XHViM2Q5XHVjMmRjXHVkMGFjIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1Yzc3NFx1YjU0Yywgalx1YjI5NCBcdWJlNDRcdWM1YjRcdWM3ODhcdWIyOTQgXHVjZTc4XHVjNzU4IFx1YmM4OFx1ZDYzOCBcdWM5MTEgXHVjZDVjXHVjMThjXHVhYzEyXHVjNzc4XHViMzcwLCBcdWIyZTRcdWI5Y2MgaVx1YmNmNFx1YjJlNFx1YjI5NCBcdWNlZTRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWFjOGNcdWM3ODRcdWM3NTggXHVjMmI5XHVjNzkwXHViMjk0IFx1YjljOFx1YzljMFx1YjljOSBcdWNlNzhcdWM3NzggbVx1YmM4OCBcdWNlNzhcdWM1ZDAgXHVkM2YwXHVjNzQ0IFx1YzlkMVx1YzViNFx1YjEyM1x1YjI5NCBcdWMwYWNcdWI3OGNcdWM3NzRcdWIyZTQuPFwvcD5cclxuPHA+PGltZyB3aWR0aD1cIjM0NFwiIGhlaWdodD1cIjc0XCIgc3JjPVwiXC9KdWRnZU9ubGluZVwvdXBsb2FkXC8yMDEwMDZcL1NjcmVlbiBzaG90IDIwMTAtMDYtMTEgYXQgOF8xNl80NCBQTS5wbmdcIiBhbHQ9XCJcIiBcLz48XC9wPlxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBtPTdcdWM3NzggXHVhZGY4XHViOWJjXHVjNzU4IFx1YzBjMVx1ZDY2OVx1YzVkMFx1YzExYyBcdWNjMjhcdWI4NDBcdWFjMDAgXHViNDFjIFx1ZDUwY1x1YjgwOFx1Yzc3NFx1YzViNFx1YjI5NCAyXHViYzg4IFx1Y2U3OFx1Yzc1OCBcdWQzZjBcdWM3NDQgNFx1YmM4OCBcdWNlNzhcdWM3M2NcdWI4NWMgXHVjNjJlXHVhZTM4IFx1YzIxOCBcdWM3ODhcdWFjZTAsIDNcdWJjODggXHVjZTc4XHVjNzU4IFx1ZDNmMFx1Yzc0NCA0XHViYzg4IFx1Y2U3OFx1YzczY1x1Yjg1YyBcdWM2MmVcdWFlMzggXHVjMjE4XHViM2M0IFx1Yzc4OFx1YzczY1x1YmE3MCwgNlx1YmM4OCBcdWNlNzhcdWM3NTggXHVkM2YwXHVjNzQ0IDdcdWJjODggXHVjZTc4XHVjNzNjXHViODVjIFx1YzYyZVx1YWNhOCBcdWFjOGNcdWM3ODRcdWM3NDQgXHVjNzc0XHVhZTM4IFx1YzIxOFx1YjNjNCBcdWM3ODhcdWIyZTQuPFwvcD48cD5cdWM1YjRcdWI1YTQgXHVkNTBjXHViODA4XHVjNzc0XHVjNWI0XHVjNzU4IFx1YzIxOFx1YWMwMCAmbHNxdW87XHVkNTQ0XHVjMmI5XHVjMjE4J1x1Yjc3Y1x1YWNlMCBcdWQ1NThcdWIyOTQgXHVhYzgzXHVjNzQwLCBcdWFkZjggXHVjMjE4XHViOTdjIFx1YjQ1NCBcdWQ2YzRcdWM1ZDQgXHVjMGMxXHViMzAwXHVkM2I4XHVjNzc0IFx1YzViNFx1YjVhNCBcdWMyMThcdWI5N2MgXHViNDUwXHViMzU0XHViNzdjXHViM2M0IFx1YmMxOFx1YjRkY1x1YzJkYyBcdWM3NzRcdWFlMzggXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFjYmRcdWM2YjBcdWI5N2MgXHViOWQwXHVkNTVjXHViMmU0LiBcdWNjYjRcdWMyYTRcdWQzMTBcdWM3NTggXHVkNjA0XHVjN2FjIFx1YzBjMVx1ZDY2OVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWM3NzRcdWJjODhcdWM1ZDAgXHVjYzI4XHViODQwXHViOTdjIFx1YjlkZVx1Yzc0MCBcdWQ1MGNcdWI4MDhcdWM3NzRcdWM1YjRcdWFjMDAgXHViNDU4IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVkNTQ0XHVjMmI5XHVjMjE4XHVjNzU4IFx1YWMwMFx1YzlkM1x1YzIxOFx1Yjk3YyBcdWFjYzRcdWMwYjBcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1Yjc3Yy4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViNDUwIFx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMTggbVx1YWNmYyBuXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDImbGU7bSZsZTsgMTBeOSwgMSZsZTtuJmxlOzEwXjYsIG5cdWZmMWNtKSBcdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IG5cdWFjMWNcdWM3NTggXHVjNTkxXHVjNzU4IFx1YzgxNVx1YzIxOFx1YWMwMCBcdWM2MjRcdWI5ODRcdWNjMjhcdWMyMWNcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0XHViMzcwLCBcdWM3NzRcdWIyOTQgXHVhYzAxXHVhYzAxIFx1ZDYwNFx1YzdhYyBcdWQzZjBcdWM3NzQgXHViMTkzXHVjNWVjIFx1Yzc4OFx1YjI5NCBcdWNlNzhcdWM3NTggXHViYzg4XHVkNjM4XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiOFx1YjJlNC4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1Yzc3NFx1YmM4OFx1YzVkMCBcdWNjMjhcdWI4NDBcdWI5N2MgXHViOWRlXHVjNzQwIFx1ZDUwY1x1YjgwOFx1Yzc3NFx1YzViNFx1YWMwMCBcdWI0NTggXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWQ1NDRcdWMyYjlcdWMyMThcdWM3NTggXHVhYzAwXHVjOWQzXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxODQyIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiR2FtZSIsImRlc2NyaXB0aW9uIjoiPHA+TGV0IHVzIGNvbnNpZGVyIGEgZ2FtZSBvbiBhIHJlY3Rhbmd1bGFyIGJvYXJkIG0gJnRpbWVzOyAxIGNvbnNpc3Rpbmcgb2YgbSBlbGVtZW50YXJ5IHNxdWFyZXMgbnVtYmVyZWQgc3VjY2Vzc2l2ZWx5IGZyb20gMSB0byBtLiBUaGVyZSBhcmUgbiBwYXducyBvbiB0aGUgYm9hcmQsIGVhY2ggb24gYSBkaXN0aW5jdCBzcXVhcmUuIE5vbmUgb2YgdGhlbSBvY2N1cGllcyB0aGUgc3F1YXJlIHdpdGggbnVtYmVyIG0uIEVhY2ggc2luZ2xlIG1vdmUgaW4gdGhlIGlzIHRoZSBmb2xsb3dpbmcgYWN0aW9uOiB0aGUgbW92aW5nIHBsYXllciBwaWNrcyBhIHBhd24gZnJvbSBhbnkgb2NjdXBpZWQgc3F1YXJlIGNob3NlbiBhdCB3aWxsIGFuZCBwbGFjZXMgaXQgb24gdGhlIGZpcnN0IHVub2NjdXBpZWQgc3F1YXJlIHdpdGggYSBsYXJnZXIgbnVtYmVyLiBUaGUgdHdvIHBsYXllcnMgbWFrZSBtb3ZlcyBpbiB0dXJuLiBUaGUgb25lIHdobyBwdXRzIGEgcGF3biBvbiB0aGUgbGFzdCBzcXVhcmUsIGkuZS4gdGhlIHNxdWFyZSB3aXRoIGEgbnVtYmVyIG0sIHdpbnMuPFwvcD5cclxuXHJcbjxwPkluIHRoZSBjYXNlIHByZXNlbnRlZCBpbiB0aGUgZmlndXJlIChtID0gNyksIGEgcGxheWVyIGlzIGFsbG93ZWQgdG8gbW92ZSBhIHBhd24gZnJvbSBzcXVhcmUgbm8uIDIgdG8gNCwgZnJvbSBzcXVhcmUgbm8uIDMgdG8gNCBvciBmcm9tIHNxdWFyZSBuby4gNiB0byA3LiBUaGUgbGF0dGVyIGVuZHMgdGhlIGdhbWUuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvZ3JhemFkLmdpZlwiIHN0eWxlPVwiaGVpZ2h0Ojg1cHg7IHdpZHRoOjQwMnB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPldlIHNheSBhIHBsYXllciYjMzk7cyBtb3ZlIGlzIHdpbm5pbmcgaWYgYWZ0ZXIgbWFraW5nIGl0IGhlIGNhbiB3aW4gdGhlIGdhbWUsIG5vIG1hdHRlciB3aGF0IG1vdmVzIGhpcyBvcHBvbmVudCBtYWtlcy48XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtbWUgdGhhdDo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5yZWFkcyB0aGUgc2l6ZSBvZiBhIGJvYXJkIGFuZCB0aGUgaW5pdGlhbCBzZXR1cCBvZiBwYXducyBmcm9tIHRoZSBzdGFuZGFyZCBpbnB1dCw8XC9saT5cclxuXHQ8bGk+ZGV0ZXJtaW5lcyB0aGUgbnVtYmVyIG9mIGRpc3RpbmN0IHdpbm5pbmcgbW92ZXMgdGhlIHN0YXJ0aW5nIHBsYXllciBtYXkgY2hvb3NlIGluIHRoZSBnaXZlbiBpbml0aWFsIHNpdHVhdGlvbiw8XC9saT5cclxuXHQ8bGk+d3JpdGVzIHRoZSByZXN1bHQgdG8gdGhlIHN0YW5kYXJkIG91dHB1dC48XC9saT5cclxuPFwvdWw+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgdGhlIGlucHV0IGNvbnRhaW5zIHR3byBpbnRlZ2VycyBtIGFuZCBuICgyICZsZTsgbSAmbGU7IDEwPHN1cD45PFwvc3VwPiwgMSAmbGU7IG4gJmxlOyAxMDxzdXA+NjxcL3N1cD4sIG4gJmx0OyBtKSBzZXBhcmF0ZWQgYnkgYSBzaW5nbGUgc3BhY2UuIFRoZSBzZWNvbmQgbGluZSBjb250YWlucyAmbmJzcDtpbmNyZWFzaW5nIG51bWJlcnMgLSB0aGVzZSBhcmUgdGhlIG51bWJlcnMgb2Ygc3F1YXJlcyB0aGUgcGF3bnMgYXJlIHNldCBvbi4gTnVtYmVycyBpbiB0aGUgbGluZSBhcmUgc2VwYXJhdGVkIGJ5IHNpbmdsZSBzcGFjZXMuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBmaXJzdCBhbmQgb25seSBvdXRwdXQgbGluZSBzaG91bGQgY29udGFpbiB0aGUgbnVtYmVyIG9mIGRpc3RpbmN0IHdpbm5pbmcgbW92ZXMgcG9zc2libGUgZm9yIHRoZSBzdGFydGluZyBwbGF5ZXIgaW4gdGhlIGdpdmVuIGluaXRpYWwgc2l0dWF0aW9uLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=