Rules#8775
Mr. Sem and Mr. Yuri, both over years old, have a peculiarly strong penchant for setting rules they believe everyone should follow. Leveraging their societal influence, they attempt to impose these rules universally.
Consider the scenario in a park with trees, all aligned in a straight line. Each tree can be visualized as a vertical segment with its base at the point (x_i, 0) and its top at (x_i, h_i), where x_i represents the tree's position along the line, and h_i is its height.
According to one of their latest rules, the top of every tree must be illuminated by a lantern. To achieve this, some trees may need to be trimmed. Specifically, a lantern is positioned at coordinates , and the rule requires that the line segment from the lantern to the top of each tree must not intersect any other tree. If a tree merely touches this segment, trimming is unnecessary. Even if a tree's height is reduced to zero, it still counts as a tree.
As participants in this challenge, your task is to determine the minimum total length by which the trees need to be trimmed to comply with the rule.
The first line contains a single integer (1 \leq n \leq 10^5) — the number of trees in the park.
Each of the following lines contains two integers x_i and h_i (0 \leq x_i \leq 10^9, 1 \leq h_i \leq 1000) — the position and height of each tree.
The next line contains two integers and (0 \leq x \leq 10^9, 1 \leq y \leq 1000) — the coordinates of the lantern.
It is guaranteed that the trees are listed in increasing order of their positions, and no tree shares the same position as the lantern.
Output a single number — the minimum total length by which the trees need to be trimmed, ensuring an absolute or relative error not exceeding 10^{-6}.
Formally, let your answer be , and the correct answer be . Your solution will be accepted if |a-b| / \max(1, |b|) \leq 10^{-6}.
Example 1