Strip

Consider a strip of width $1$, length $n$, and negligible thickness, divided into unit squares. Starting from its left end, label each of the vertical creases with the integers $0$ to $n$, as shown in the picture (where $n = 7$). The strip may be folded only along these creases; once folded, the two overlapping parts are glued together and never straightened again.

After a fold, some labelled creases come to lie exactly on top of one another, forming a single position that therefore carries several labels. For example, folding the $n = 7$ strip along crease $3$ makes crease $1$ and crease $5$ coincide, so from then on "$1$" and "$5$" denote the same crease. Folding again along crease $2$ (equivalently, along crease $4$, which is now the same position) produces a position with three labels, $\{1, 3, 5\}$.

If the fold happens to lie exactly on an end of the current strip, it changes neither the labelling nor the length. Such a fold is not forbidden; it is simply an empty fold.

A sequence of $k$ integers, each between $0$ and $n$, therefore defines a sequence of folds. Determine the length of the strip after all $k$ folds have been applied in order.

The input is given on standard input.

• Line $1$: two space-separated positive integers $n$ and $k$.
• Line $2$: $k$ space-separated non-negative integers, each at most $n$ — the creases to fold along, in order.

Print a single line containing one integer: the length of the strip after all $k$ folds have been applied consecutively.

• $n$ is a positive integer with at most $18$ decimal digits.
• $1 \le k \le 10000$.
• Each fold value is an integer in the range $[0, n]$.

For the second test case ($n = 9$, folds $5\ 9\ 2\ 8\ 3$), the positions and their labels evolve as shown below. Labels grouped in parentheses share a single position.

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

• fold $5$: $\{0\ (1;9)\ (2;8)\ (3;7)\ (4;6)\ 5\}$
• fold $9$: $\{(1;9)\ (0;2;8)\ (3;7)\ (4;6)\ 5\}$
• fold $2$: $\{(0;2;8)\ (1;3;7;9)\ (4;6)\ 5\}$
• fold $8$: $\{(0;2;8)\ (1;3;7;9)\ (4;6)\ 5\}$ (an empty fold — crease $8$ already sits at an end)
• fold $3$: $\{(1;3;7;9)\ (0;2;4;6;8)\ 5\}$

Three positions remain, so the final length is $2$.