Election of the Leader#176
In the world of Draenor, orcs are a formidable race known for their strength and courage in battle, though not particularly for their intelligence. Each year, orcs from various clans gather in the Valley of Strength to select the leader of the Horde. Unlike humans, orcs do not use votes, ballots, or polling stations—these are foreign concepts to them. Instead, they determine their leader through a series of fair duels.
In each duel, two candidates face off, with one emerging as the victor and the other being defeated. An orc who loses a duel is eliminated and cannot participate in any subsequent contests. The last orc remaining after all duels becomes the leader of the Horde.
The orc elders, who oversee these contests, enjoy predicting the outcomes. However, predicting the overall winner or even the victor of a specific duel is not always straightforward. The outcome depends on the strength of the opponents: usually, the stronger orc wins. But if two orcs have equal strength, the result is uncertain and could go either way, depending on fate.
The elders have asked you to develop a program that determines how many contenders have a chance to become the leader.
The first line contains the number of contenders for the leadership this year (1 \le N \le 1\,000\,000). The second line contains integers, each from to , representing the strength of each candidate.
Output one integer—the number of contenders who have a chance to become the leader.
Example 1