Zoran wanders across his Dalmatian homeland to forget his love woes. He came across a mountain of a
specific shape, behind which a young maiden is waiting for him. The mountain can be described with
\(n\) alternating low and high points, where \(n\) is odd. Points at odd indices, except the first and the last
point, are called valleys.
Zoran is afraid of the dark. Even the call of love will not give him courage to cross the mountain at night.
As usual, the fairies of Velebit come to the rescue.
We model each fairy by a luminous dot at a fixed height \(h\). A fairy illuminates the valley if and only if
the segment connecting the fairy and the valley does not intersect the interior of the mountain.
The mountain from the first example, and a fairy illuminating all three valleys.
What is the least number of fairies which can illuminate all the valleys simulaneously?

Subtask 1 (20 points): \(y@@RISE_MATH_BLOCK_0@@n - 1\)

Subtask 2 (30 points): \(3 \le n < 2000\)

Subtask 3 (60 points): No additional constraints.

The first line contains two integers \(n\) (\(3 \le n < 10^{6}\), \(n\) odd) and \(h\) (\(1 \le h \le 10^{6}\)), the number of points
describing the mountain and the height the fairies live at.
The \(i-th\) of the following \(n\) lines contains integers \(x@@RISE_MATH_BLOCK_0@@i\) (−\(10^{6} \le x@@RISE_MATH_BLOCK_1@@i < h\)), the coordinates
of the \(i-th\) point of the mountain.
It is guaranteed that \(x@@RISE_MATH_BLOCK_2@@1 < y\)2, \(y@@RISE_MATH_BLOCK_3@@3 < y\)4, . . ., \(y@@RISE_MATH_BLOCK_4@@n\).

Output the least number of fairies such that all valleys are illuminated.

생성자가 기록되지 않았습니다.

출처 COCI 2020/2021 Contest 5