P10695 [SNCPC2024] Trade Routes.

A circle is divided into $K$ equal parts by $K$ points, numbered clockwise as $1, 2, \cdots, K$. Among them, points $a_1, a_2, \cdots, a_n$ each have a market $M_1, M_2, \cdots, M_n$ built on them. A trade route starting from market $i$ and aiming at market $j$ is a directed line segment $M_i M_j$ ($i \neq j$), and it must satisfy the following conditions: - Market $j$ must be the farthest market from market $i$ (if there are multiple farthest markets at the same distance, any one of them is allowed). - The trade route segment $M_i M_j$ must not intersect or overlap with any other trade route segment at any place other than their starting points or ending points. What is the maximum number of trade routes that can exist?

The first line contains two integers $K, n$ ($3 \leq K \leq 10^9, 3\leq n \leq \min(K,10^5)$), separated by spaces, meaning that $n$ markets are placed on the $K$ equally divided points on the circle. The second line contains $n$ integers $a_1, a_2, \cdots, a_n$ ($1\leq a_1 < a_2 < \cdots < a_{n-1} < a_n \leq K$), which are the indices of the points where markets are built.

Output one integer, the maximum number of trade routes that can exist.

For the first sample, two possible answers are shown in the figures below:   Translated by ChatGPT 5