P15986 [PA 2026] Necklace / Naszyjnik

Bajtazar’s wife bought a beautiful necklace. A number of pearls are attached in order on a chain that forms a circular loop. When the necklace is worn, all the pearls are in front of the neck, and behind the head there is a segment of the chain with no pearls. However, the pearls are not fixed permanently on the chain: you can move any number of pearls from one end along the chain, over the head, to the other end of the necklace. As a pearl expert, Bajtazar will carefully examine every pearl on the necklace one by one from left to right. Each pearl has a beauty level. Whenever Bajtazar sees a pearl that is more beautiful than all the pearls he has seen before, he will exclaim in admiration. Bajtazar’s wife likes to see Bajtazar exclaim, so she wants to adjust the order of the pearls by moving some pearls from one end to the other, so that he will exclaim as many times as possible. Compute the maximum possible number of exclamations. Note that the pearls look good only from the front, so the necklace cannot be flipped (i.e., mirrored left to right). Of course, you also cannot take pearls off the necklace and rearrange them into a completely different order.

The first line contains an integer $n$ $(1 \le n \le 1\ 000\ 000)$, the number of pearls on the necklace. The second line contains $n$ integers $a_1, \dots, a_n$ $(1 \le a_i \le 1\ 000\ 000)$, the beauty levels of the pearls in order.

Output the maximum integer $k$ such that, after moving some number of pearls from the beginning of the necklace to the end (without changing their internal order), the necklace contains exactly $k$ pearls whose beauty level $a_i$ is strictly greater than the beauty levels of all pearls before them.

### Sample Explanation In the original order (left figure), Bajtazar will exclaim three times: when he sees the first pearl, then the second pearl, and then the last pearl. In particular, when he sees the pearl with beauty level $7$ again, he will not exclaim. But if the first two pearls are moved to the end (right figure), Bajtazar will exclaim four times: when he first sees beauty levels $2$, $3$, $7$, and $9$, respectively. ::::aligned{center}  :::: Translated by ChatGPT 5