종이띠 접기

폭이 $1$, 길이가 $n$, 두께는 무시할 수 있는 종이띠가 단위 정사각형들로 나뉘어 있다. 왼쪽 끝에서부터 시작하여, 그림처럼(그림은 $n = 7$인 경우) 접을 수 있는 각 세로 경계선에 $0$부터 $n$까지의 정수를 차례로 이름 붙인다. 종이띠는 오직 이 경계선을 따라서만 접을 수 있으며, 한 번 접으면 겹쳐진 두 부분은 서로 붙어 다시 펴지지 않는다.

접고 나면 이름이 붙은 몇몇 경계선이 서로 정확히 포개져 하나의 위치를 이루고, 그 위치는 여러 개의 이름을 가지게 된다. 예를 들어 $n = 7$인 띠를 경계선 $3$에서 접으면 $1$번과 $5$번이 같은 위치에 놓여, 이후로는 "$1$"과 "$5$"가 같은 경계선을 가리킨다. 이어서 경계선 $2$(같은 위치가 된 $4$라고 해도 된다)에서 다시 접으면 $\{1, 3, 5\}$처럼 이름이 세 개인 위치가 생긴다.

접는 위치가 현재 띠의 양 끝 중 하나에 정확히 놓여 있다면, 그 접기는 이름 배치도 길이도 바꾸지 않는다. 이런 접기는 금지된 것은 아니며, 그저 아무 변화도 없는 빈 접기일 뿐이다.

따라서 각각 $0$부터 $n$ 사이의 정수 $k$개로 이루어진 수열은 하나의 접기 순서를 정의한다. 이 $k$번의 접기를 순서대로 모두 수행한 뒤 종이띠의 길이를 구하라.

입력은 표준 입력으로 주어진다.

• 첫째 줄: 공백으로 구분된 두 양의 정수 $n$과 $k$.
• 둘째 줄: 공백으로 구분된 음이 아닌 정수 $k$개. 각 값은 $n$ 이하이며, 접을 경계선을 접는 순서대로 나타낸다.

$k$번의 접기를 순서대로 모두 수행한 뒤 남은 종이띠의 길이를 정수 하나로 한 줄에 출력한다.

• $n$은 양의 정수이며, 십진수로 나타냈을 때 자릿수가 최대 $18$자리이다.
• $1 \le k \le 10000$.
• 각 접기 값은 $[0, n]$ 범위의 정수이다.

두 번째 테스트 케이스($n = 9$, 접는 순서 $5\ 9\ 2\ 8\ 3$)에서 각 위치와 그 이름들이 어떻게 변하는지 살펴보자. 괄호로 묶인 이름들은 같은 위치에 포개진 것이다.

시작: $\{0\ 1\ 2\ 3\ 4\ 5\ 6\ 7\ 8\ 9\}$

• $5$번 접기: $\{0\ (1;9)\ (2;8)\ (3;7)\ (4;6)\ 5\}$
• $9$번 접기: $\{(1;9)\ (0;2;8)\ (3;7)\ (4;6)\ 5\}$
• $2$번 접기: $\{(0;2;8)\ (1;3;7;9)\ (4;6)\ 5\}$
• $8$번 접기: $\{(0;2;8)\ (1;3;7;9)\ (4;6)\ 5\}$ ($8$번 경계선이 이미 끝에 있으므로 빈 접기)
• $3$번 접기: $\{(1;3;7;9)\ (0;2;4;6;8)\ 5\}$

위치가 세 개 남았으므로 최종 길이는 $2$이다.