Bajtazar 的妻子买了一条漂亮的项链，由若干颗珍珠依次串在一个圆环形的链子上。当项链戴上时，所有的珍珠都在脖子前方，而脑后是一段没有珍珠的链子。然而，珍珠并不是固定在链子上的：可以将任意数量的末端珍珠沿着链子拉到脑后，并放置在项链的另一端。
Bajtazar 作为一名珍珠鉴赏家，一定会仔细观察项链中的每一颗珍珠，从左到右进行分析。我们可以为每一颗珍珠分配一个美丽度等级。每当 Bajtazar 看到一颗比之前所有珍珠都更美丽的珍珠时，他就会感到惊叹。
Bajtazar 的妻子喜欢看到 Bajtazar 惊叹，因此她想通过移动项链中的珍珠（将一部分珍珠从一端移到另一端），使得他惊叹的次数尽可能多。请计算这个最大次数。
请注意，项链上的珍珠只有正面是好看的，因此不能将项链翻转（即左右镜像）。当然，也不能将珍珠从链子上取下来并以完全不同的顺序重新排列。
输入格式
第一行包含一个整数 $n$ ($1 \le n \le 1\,000\,000$)，表示项链中珍珠的数量。第二行包含一个由 $n$ 个整数组成的序列 $a_1, \dots, a_n$ ($1 \le a_i \le 1\,000\,000$)，表示项链中各颗珍珠的美丽度等级。
输出格式
输出最大的整数 $k$，使得在将项链开头的若干颗珍珠移动到末尾（保持它们的相对顺序不变）后，项链中会有 $k$ 颗珍珠，其美丽度等级 $a_i$ 严格大于之前所有珍珠的美丽度等级。
样例
输入 1
7 1 7 2 3 7 2 9
输出 1
4
说明 1
在原始项链排列中（左图），Bajtazar 会惊叹三次：看到第一颗珍珠时，看到第二颗珍珠时，以及看到最后一颗珍珠时；特别地，他不会在再次看到美丽度为 $7$ 的珍珠时惊叹。然而，如果将前两颗珍珠移到末尾（右图），Bajtazar 将会惊叹四次：分别是在第一次看到美丽度为 $2, 3, 7$ 和 $9$ 的珍珠时。
