Non‐Intersecting Antipodal Business Routes

Consider a circle on which $K$ equally–spaced points are marked with clockwise labels $1,2,\dots,K$. Among these points, markets $M_1,M_2,\dots,M_n$ are constructed at positions $a_1,a_2,\dots,a_n$ (given as a sorted list of point labels). For each market $M_i$ (with angle $$\theta_i=2\pi\frac{a_i-1}{K}$$), we define its valid business route(s) as a directed segment from $M_i$ to some other market $M_j\ (i\neq j)$ such that:

1. The target market $M_j$ is one of the farthest markets from $M_i$, that is, $$M_j;\text{maximizes}; d(M_i,M_k);\text{for }k\neq i,$$ where the distance is measured by the chord length. (Equivalently, if we define

$$d(M_i,M_k)=2R\;\sin\Bigl(\frac{\min(|\theta_i-\theta_k|,2\pi-|\theta_i-\theta_k|)}{2}\Bigr), $$

then $M_j$ is chosen so that $$d(M_i,M_j)=\max_{k\neq i} d(M_i,M_k).$$ In the case of a tie (which may happen, for example, when the markets form a regular polygon) any of the farthest markets may be chosen.

2. No two chosen business routes (drawn as the straight line segments connecting the corresponding markets) are allowed to intersect or coincide at any interior point (they may meet at endpoints).

Your task is to select a subset of the valid business routes so that the number of routes is maximized and the non–intersection constraint is satisfied. Note that if two valid routes share an endpoint, that is allowed.

For example, if the markets are placed so that they form a square (with $n=4$ and the farthest from each market is unique – namely the diametrically opposite market), the only valid routes (as undirected segments) are the two diameters; however, since any two different diameters intersect at the center, at most one business route can be chosen. In contrast, when the markets form an equilateral triangle ($n=3$) every market has two farthest choices (in fact every edge is valid) and all three edges may be chosen (since the edges meet only at vertices).

It can be shown that, given the positions of the markets, the valid routes (if we remove duplicate oppositely–directed edges) form a set $E$ of chords on a circle. Two chords from $E$ conflict (i.e. they intersect in a point other than an endpoint) if and only if they do not share an endpoint and their endpoints are interlaced in the circle – more precisely, if after identifying each chord $(M_i,M_j)$ with the unordered pair $\{i,j\}$ (with angles normalized so that the chord always represents the shorter arc, expressed in (\LaTeX) as

$$\{\theta_a,\theta_b\}\n\quad\text{with} \quad \theta_a<\theta_b\quad \text{and} \quad \theta_b-\theta_a\le \pi), $$

then two chords $(M_i,M_j)$ and $(M_k,M_l)$ (with normalized endpoints $\theta_a,\theta_b$ and $\theta_c,\theta_d$, and assuming $\theta_a<\theta_c$) intersect if and only if $$\theta_a<\theta_c<\theta_b<\theta_d.$$

Your job is to compute the maximum number of business routes that can be chosen from the candidate set $E$ so that no two non–adjacent chords intersect.

Input and output formats are described below.

inputFormat

The first line contains two integers $K$ and $n$ ($n\le K$). The second line contains $n$ distinct integers $a_1,a_2,\dots,a_n$ in increasing order (each between $1$ and $K$) indicating the positions (labels) where the markets are built.

outputFormat

Output a single integer – the maximum number of business routes (i.e. non–intersecting chords chosen among the candidate valid routes) that can be selected.

sample

4 4
1 2 3 4

1