Problem Statement

RiRinbaru was happily making an Amidakuji (ladder lottery) using the matchsticks he had at home.

First, RiRinbaru drew $N$ sufficiently long vertical lines in parallel at intervals of length $1$. He builds the Amidakuji by placing matchsticks so that they bridge these lines. He places $M$ matchsticks of length $1$, each connecting $2$ adjacent vertical lines. The $i$-th matchstick from the top was placed so that its left vertical line is the $S_i$-th from the left.
Two results of an Amidakuji are considered different if the endpoint reached from some starting point differs.

RiRinbaru was having fun, but his mother told him she wanted a matchstick, so he must choose $1$ of the matchsticks he was using and remove it from the Amidakuji.
How many different results are possible for the Amidakuji obtained by removing $1$ horizontal stick from it?

Input

$N\ M$
$S_1\ S_2\ ...\ S_M$

• $2\leq N\leq 10^5$
• $1\leq M\leq 10^5$
• $1\leq S_i< N$
• All inputs are integers.

Output

Output the number of possible kinds of final results.
Print a newline at the end.

Sample

3 4
1 2 1 1

3

4 10
1 3 1 2 3 2 3 2 1 3

4