폰 게임의 필승수

1행 m열 직사각형 판에서 하는 게임을 생각하자. 칸에는 1번부터 m번까지 번호가 붙어 있다. n개의 폰이 서로 다른 칸에 하나씩 놓여 있고, m번 칸은 비어 있다.

두 플레이어가 번갈아 한 번씩 둔다. 자기 차례에는 i번 칸에 있는 폰 하나를 골라 j번 칸으로 옮겨야 한다. 여기서 j는 i보다 큰 빈 칸 중 번호가 가장 작은 칸이다. 즉, 선택한 폰의 오른쪽에서 처음 만나는 빈 칸으로 옮긴다.

폰을 m번 칸으로 옮긴 플레이어가 즉시 이긴다. 현재 배치에서 차례인 플레이어가 둘 수 있는 합법적인 수 중 필승수의 개수를 구하라. 필승수란 그 수를 둔 뒤 상대가 어떻게 응수하더라도 현재 플레이어가 승리를 강제할 수 있는 수를 말한다.

첫째 줄에 두 양의 정수 m과 n이 주어진다.

• 2 <= m <= 10^9
• 1 <= n <= 10^6
• n < m

둘째 줄에는 현재 폰이 놓인 칸 번호를 나타내는 n개의 양의 정수가 오름차순으로 주어진다. m번 칸은 비어 있다.

이번에 차례인 플레이어가 둘 수 있는 필승수의 개수를 출력한다.