[AdditionalFile5684.zip](file://AdditionalFile5684.zip?type=additional_file)

#5684. 「PA 2026」Naszyjnik

标签: 传统 | 时间限制: 1000 ms | 内存限制: 1024 MiB |

题目描述

题目译自 PA 2026 Runda 4 Naszyjnik

Bajtazar 的妻子买了一条漂亮的项链，由若干颗珍珠串在圆环状的链条上组成。当戴上项链时，所有珍珠都位于脖子前方，而后脑勺处是一段没有珍珠的链条。这些珍珠并没有固定在链条上：你可以将任意数量的边缘珍珠沿着链条滑到项链的另一端。

Bajtazar 是一位珍珠鉴赏大师，他会从左到右依次观察项链上的珍珠。我们可以为每颗珍珠赋予一个美丽值。只要 Bajtazar 看到一颗比之前所有珍珠都更美的珍珠，他就会感到惊叹。

Bajtazar 的妻子喜欢看到他惊叹的样子，因此她想重新排列项链上的珍珠（通过将一部分珍珠从一端移到另一端），使得他惊叹的次数尽可能多。请计算这个最大的惊叹次数。

请注意，项链上的珍珠只有正面才好看，因此不能将项链翻转（左右反射）。当然，也不能将珍珠从链条上取下来并以完全不同的顺序重新排列。

输入格式

第一行包含一个整数 $n$ $(1 \leq n \leq 1000000)$，表示项链上的珍珠数量。

第二行包含 $n$ 个整数 $a_{1}, \ldots, a_{n}$ $(1 \leq a_{i} \leq 1000000)$，表示项链上依次排列的珍珠的美丽值。

输出格式

输出最大的整数 $k$，使得通过将项链开头的一定数量珍珠移到末尾（不改变珍珠间的相对顺序），项链中会有 $k$ 颗珍珠，其美丽值 $a_{i}$ 严格大于之前所有珍珠的美丽值。

样例

输入

7
1 7 2 3 7 2 9

输出

4

在项链的原始排列中（左图），Bajtazar 会惊叹三次：看到第一颗珍珠时，看到第二颗珍珠时，以及看到最后一颗珍珠时；特别地，当他再次看到美丽值为 $7$ 的珍珠时，他不会惊叹。然而，如果将前两颗珍珠移到末尾（右图），Bajtazar 会惊叹四次：分别是第一次看到美丽值为 $2, 3, 7$ 和 $9$ 的珍珠时。