시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 144 32 19 18.447%

문제

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
W3sicHJvYmxlbV9pZCI6IjE4NDIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjOGNcdWM3ODRcdWQ1NThcdWFlMzAiLCJkZXNjcmlwdGlvbiI6IjxwPjFcdWQ1ODkgbVx1YzVmNFx1Yzc1OCBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTUgXHVjY2I0XHVjMmE0XHVkMzEwIFx1YzcwNFx1YzVkMFx1YzExYyBcdWM5YzRcdWQ1ODlcdWQ1NThcdWIyOTQgXHVhYzhjXHVjNzg0XHVjNzQ0IFx1YWMwMFx1YzgxNVx1ZDU3NCBcdWJjZjRcdWM3OTAuIFx1Y2NiNFx1YzJhNFx1ZDMxMFx1Yzc1OCBcdWFjMDEgXHVjZTc4XHVjNWQwXHViMjk0IDFcdWJkODBcdWQxMzAgbVx1YWU0Y1x1YzljMCBcdWJjODhcdWQ2MzhcdWFjMDAgXHViOWU0XHVhY2E4XHVjODM4IFx1Yzc4OFx1YjJlNC4gblx1YWMxY1x1Yzc1OCBcdWQzZjAgKHBhd24pXHVjNzc0IFx1ZDU1OFx1YjA5OFx1YzUyOVx1Yzc1OCBcdWNlNzhcdWM3NDQgXHVjYzI4XHVjOWMwXHVkNTVjIFx1Y2M0NFx1Yjg1YyBcdWNjYjRcdWMyYTRcdWQzMTAgXHVjNzA0XHVjNWQwIFx1YjE5M1x1YzVlYyBcdWM3ODhcdWM3M2NcdWJhNzAsIG1cdWJjODggXHVjZTc4XHVjNzQwIFx1YmU0NFx1YzViNCBcdWM3ODhcdWIyZTQuIFx1YjQ1MCBcdWJhODVcdWM3NTggXHVkNTBjXHViODA4XHVjNzc0XHVjNWI0XHVhYzAwIFx1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWQ1NWNcdWIyZTQuIFx1YWMwMSBcdWQ1MGNcdWI4MDhcdWM3NzRcdWM1YjRcdWIyOTQgXHVjNzkwXHVhZTMwIFx1Y2MyOFx1Yjg0MFx1YWMwMCBcdWM2MjRcdWJhNzQgaVx1YmM4OCBcdWNlNzhcdWM1ZDAgXHViMTkzXHVjNzc4IFx1ZDNmMFx1Yzc0NCBcdWM5ZDFcdWM1YjRcdWMxMWMgalx1YmM4OCBcdWNlNzhcdWM3M2NcdWI4NWMgXHVjNzc0XHViM2Q5XHVjMmRjXHVkMGFjIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1Yzc3NFx1YjU0Yywgalx1YjI5NCBcdWJlNDRcdWM1YjRcdWM3ODhcdWIyOTQgXHVjZTc4XHVjNzU4IFx1YmM4OFx1ZDYzOCBcdWM5MTEgXHVjZDVjXHVjMTlmXHVhYzEyXHVjNzc4XHViMzcwLCBcdWIyZTRcdWI5Y2MgaVx1YmNmNFx1YjJlNFx1YjI5NCBcdWNlZTRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWFjOGNcdWM3ODRcdWM3NTggXHVjMmI5XHVjNzkwXHViMjk0IFx1YjljOFx1YzljMFx1YjljOSBcdWNlNzhcdWM3NzggbVx1YmM4OCBcdWNlNzhcdWM1ZDAgXHVkM2YwXHVjNzQ0IFx1YzlkMVx1YzViNFx1YjEyM1x1YjI5NCBcdWMwYWNcdWI3OGNcdWM3NzRcdWIyZTQuPFwvcD5cclxuPHA+PGltZyB3aWR0aD1cIjM0NFwiIGhlaWdodD1cIjc0XCIgc3JjPVwiXC9KdWRnZU9ubGluZVwvdXBsb2FkXC8yMDEwMDZcL1NjcmVlbiBzaG90IDIwMTAtMDYtMTEgYXQgOF8xNl80NCBQTS5wbmdcIiBhbHQ9XCJcIiBcLz48XC9wPlxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBtPTdcdWM3NzggXHVhZGY4XHViOWJjXHVjNzU4IFx1YzBjMVx1ZDY2OVx1YzVkMFx1YzExYyBcdWNjMjhcdWI4NDBcdWFjMDAgXHViNDFjIFx1ZDUwY1x1YjgwOFx1Yzc3NFx1YzViNFx1YjI5NCAyXHViYzg4IFx1Y2U3OFx1Yzc1OCBcdWQzZjBcdWM3NDQgNFx1YmM4OCBcdWNlNzhcdWM3M2NcdWI4NWMgXHVjNjJlXHVhZTM4IFx1YzIxOCBcdWM3ODhcdWFjZTAsIDNcdWJjODggXHVjZTc4XHVjNzU4IFx1ZDNmMFx1Yzc0NCA0XHViYzg4IFx1Y2U3OFx1YzczY1x1Yjg1YyBcdWM2MmVcdWFlMzggXHVjMjE4XHViM2M0IFx1Yzc4OFx1YzczY1x1YmE3MCwgNlx1YmM4OCBcdWNlNzhcdWM3NTggXHVkM2YwXHVjNzQ0IDdcdWJjODggXHVjZTc4XHVjNzNjXHViODVjIFx1YzYyZVx1YWNhOCBcdWFjOGNcdWM3ODRcdWM3NDQgXHVjNzc0XHVhZTM4IFx1YzIxOFx1YjNjNCBcdWM3ODhcdWIyZTQuPFwvcD48cD5cdWM1YjRcdWI1YTQgXHVkNTBjXHViODA4XHVjNzc0XHVjNWI0XHVjNzU4IFx1YzIxOFx1YWMwMCAmbHNxdW87XHVkNTQ0XHVjMmI5XHVjMjE4J1x1Yjc3Y1x1YWNlMCBcdWQ1NThcdWIyOTQgXHVhYzgzXHVjNzQwLCBcdWFkZjggXHVjMjE4XHViOTdjIFx1YjQ1NCBcdWQ2YzRcdWM1ZDQgXHVjMGMxXHViMzAwXHVkM2I4XHVjNzc0IFx1YzViNFx1YjVhNCBcdWMyMThcdWI5N2MgXHViNDUwXHViMzU0XHViNzdjXHViM2M0IFx1YmMxOFx1YjRkY1x1YzJkYyBcdWM3NzRcdWFlMzggXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFjYmRcdWM2YjBcdWI5N2MgXHViOWQwXHVkNTVjXHViMmU0LiBcdWNjYjRcdWMyYTRcdWQzMTBcdWM3NTggXHVkNjA0XHVjN2FjIFx1YzBjMVx1ZDY2OVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWM3NzRcdWJjODhcdWM1ZDAgXHVjYzI4XHViODQwXHViOTdjIFx1YjlkZVx1Yzc0MCBcdWQ1MGNcdWI4MDhcdWM3NzRcdWM1YjRcdWFjMDAgXHViNDU4IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVkNTQ0XHVjMmI5XHVjMjE4XHVjNzU4IFx1YWMwMFx1YzlkM1x1YzIxOFx1Yjk3YyBcdWFjYzRcdWMwYjBcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1Yjc3Yy4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViNDUwIFx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMTggbVx1YWNmYyBuXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDImbGU7bSZsZTsgMTBeOSwgMSZsZTtuJmxlOzEwXjYsIG5cdWZmMWNtKSBcdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IG5cdWFjMWNcdWM3NTggXHVjNTkxXHVjNzU4IFx1YzgxNVx1YzIxOFx1YWMwMCBcdWM2MjRcdWI5ODRcdWNjMjhcdWMyMWNcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0XHViMzcwLCBcdWM3NzRcdWIyOTQgXHVhYzAxXHVhYzAxIFx1ZDYwNFx1YzdhYyBcdWQzZjBcdWM3NzQgXHViMTkzXHVjNWVjIFx1Yzc4OFx1YjI5NCBcdWNlNzhcdWM3NTggXHViYzg4XHVkNjM4XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiOFx1YjJlNC4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1Yzc3NFx1YmM4OFx1YzVkMCBcdWNjMjhcdWI4NDBcdWI5N2MgXHViOWRlXHVjNzQwIFx1ZDUwY1x1YjgwOFx1Yzc3NFx1YzViNFx1YWMwMCBcdWI0NTggXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWQ1NDRcdWMyYjlcdWMyMThcdWM3NTggXHVhYzAwXHVjOWQzXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjE4NDIiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJHYW1lIiwiZGVzY3JpcHRpb24iOiI8cD5MZXQgdXMgY29uc2lkZXIgYSBnYW1lIG9uIGEgcmVjdGFuZ3VsYXIgYm9hcmQgbSAmdGltZXM7IDEgY29uc2lzdGluZyBvZiBtIGVsZW1lbnRhcnkgc3F1YXJlcyBudW1iZXJlZCBzdWNjZXNzaXZlbHkgZnJvbSAxIHRvIG0uIFRoZXJlIGFyZSBuIHBhd25zIG9uIHRoZSBib2FyZCwgZWFjaCBvbiBhIGRpc3RpbmN0IHNxdWFyZS4gTm9uZSBvZiB0aGVtIG9jY3VwaWVzIHRoZSBzcXVhcmUgd2l0aCBudW1iZXIgbS4gRWFjaCBzaW5nbGUgbW92ZSBpbiB0aGUgaXMgdGhlIGZvbGxvd2luZyBhY3Rpb246IHRoZSBtb3ZpbmcgcGxheWVyIHBpY2tzIGEgcGF3biBmcm9tIGFueSBvY2N1cGllZCBzcXVhcmUgY2hvc2VuIGF0IHdpbGwgYW5kIHBsYWNlcyBpdCBvbiB0aGUgZmlyc3QgdW5vY2N1cGllZCBzcXVhcmUgd2l0aCBhIGxhcmdlciBudW1iZXIuIFRoZSB0d28gcGxheWVycyBtYWtlIG1vdmVzIGluIHR1cm4uIFRoZSBvbmUgd2hvIHB1dHMgYSBwYXduIG9uIHRoZSBsYXN0IHNxdWFyZSwgaS5lLiB0aGUgc3F1YXJlIHdpdGggYSBudW1iZXIgbSwgd2lucy48XC9wPlxyXG5cclxuPHA+SW4gdGhlIGNhc2UgcHJlc2VudGVkIGluIHRoZSBmaWd1cmUgKG0gPSA3KSwgYSBwbGF5ZXIgaXMgYWxsb3dlZCB0byBtb3ZlIGEgcGF3biBmcm9tIHNxdWFyZSBuby4gMiB0byA0LCBmcm9tIHNxdWFyZSBuby4gMyB0byA0IG9yIGZyb20gc3F1YXJlIG5vLiA2IHRvIDcuIFRoZSBsYXR0ZXIgZW5kcyB0aGUgZ2FtZS48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9ncmF6YWQuZ2lmXCIgc3R5bGU9XCJoZWlnaHQ6ODVweDsgd2lkdGg6NDAycHhcIiBcLz48XC9wPlxyXG5cclxuPHA+V2Ugc2F5IGEgcGxheWVyJiMzOTtzIG1vdmUgaXMgd2lubmluZyBpZiBhZnRlciBtYWtpbmcgaXQgaGUgY2FuIHdpbiB0aGUgZ2FtZSwgbm8gbWF0dGVyIHdoYXQgbW92ZXMgaGlzIG9wcG9uZW50IG1ha2VzLjxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW1tZSB0aGF0OjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPnJlYWRzIHRoZSBzaXplIG9mIGEgYm9hcmQgYW5kIHRoZSBpbml0aWFsIHNldHVwIG9mIHBhd25zIGZyb20gdGhlIHN0YW5kYXJkIGlucHV0LDxcL2xpPlxyXG5cdDxsaT5kZXRlcm1pbmVzIHRoZSBudW1iZXIgb2YgZGlzdGluY3Qgd2lubmluZyBtb3ZlcyB0aGUgc3RhcnRpbmcgcGxheWVyIG1heSBjaG9vc2UgaW4gdGhlIGdpdmVuIGluaXRpYWwgc2l0dWF0aW9uLDxcL2xpPlxyXG5cdDxsaT53cml0ZXMgdGhlIHJlc3VsdCB0byB0aGUgc3RhbmRhcmQgb3V0cHV0LjxcL2xpPlxyXG48XC91bD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiB0aGUgaW5wdXQgY29udGFpbnMgdHdvIGludGVnZXJzIG0gYW5kIG4gKDIgJmxlOyBtICZsZTsgMTA8c3VwPjk8XC9zdXA+LCAxICZsZTsgbiAmbGU7IDEwPHN1cD42PFwvc3VwPiwgbiAmbHQ7IG0pIHNlcGFyYXRlZCBieSBhIHNpbmdsZSBzcGFjZS4gVGhlIHNlY29uZCBsaW5lIGNvbnRhaW5zICZuYnNwO2luY3JlYXNpbmcgbnVtYmVycyAtIHRoZXNlIGFyZSB0aGUgbnVtYmVycyBvZiBzcXVhcmVzIHRoZSBwYXducyBhcmUgc2V0IG9uLiBOdW1iZXJzIGluIHRoZSBsaW5lIGFyZSBzZXBhcmF0ZWQgYnkgc2luZ2xlIHNwYWNlcy48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIGZpcnN0IGFuZCBvbmx5IG91dHB1dCBsaW5lIHNob3VsZCBjb250YWluIHRoZSBudW1iZXIgb2YgZGlzdGluY3Qgd2lubmluZyBtb3ZlcyBwb3NzaWJsZSBmb3IgdGhlIHN0YXJ0aW5nIHBsYXllciBpbiB0aGUgZ2l2ZW4gaW5pdGlhbCBzaXR1YXRpb24uPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d