E. Trade Road
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

A circle is divided into $$$K$$$ points which are numbered clockwise as $$$1, 2, \cdots, K$$$. Among them, markets $$$M_1, M_2, \cdots, M_n$$$ are built at points $$$a_1, a_2, \cdots, a_n$$$ respectively.

A trade route from market $$$i$$$ to market $$$j$$$ is a directed line segment $$$M_i M_j$$$ ($$$i \neq j$$$) and must satisfy the following conditions:

  • Market $$$j$$$ must be the farthest market from market $$$i$$$ (if there are multiple markets at the same farthest distance, any one of them is acceptable).
  • The route segment $$$M_i M_j$$$ cannot intersect or overlap with other route segments at points other than the starting or ending points.

What is the maximum number of trade routes that can exist?

Input

The first line contains two integers $$$K$$$, $$$n$$$ ($$$3 \leq K \leq 10^9, 3\leq n \leq \min(K,10^5) $$$), separated by a space, representing that there are $$$n$$$ markets distributed at the $$$K$$$ equally spaced points on the circle.

The second line contains $$$n$$$ integers $$$a_1, a_2, \cdots, a_n$$$ ($$$1\leq a_1 \lt a_2 \lt \cdots \lt a_{n-1} \lt a_n \leq K$$$), correspond to points at which a market is built.

Output

Output an integer representing the maximum number of trade routes that can exist.

Examples
Input
10 5
1 2 5 6 8
Output
2
Input
3 3
1 2 3
Output
3
Note

For the first example, the two possible answers are shown in the following figures: