题目描述

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$ 严格大于其之前所有珍珠的美丽度。

7
1 7 2 3 7 2 9

4

提示

样例解释

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

::::aligned{center} ::::