Alice and Bob

题目描述

Alice 和 Bob 发明了一个新的游戏。给定一个序列$\{x_0, x_1, \cdots, x_{n - 1}\}$。Alice 得到一个序列$\{a_0, a_1, \cdots, a_{n - 1}\}$，其中$a_i$表示以$x_i$结尾的最长上升子序列的长度；Bob 得到一个序列$\{b_0, b_1, \cdots, b_{n - 1}\}$，其中$b_i$表示以$x_i$开头的最长下降子序列的长度。Alice 的得分是序列$\{a_0, a_1, \cdots, a_{n - 1}\}$的和，Bob 的得分是序列$\{b_0, b_1, \cdots, b_{n - 1}\}$的和。

输入格式

输入的第一行是$n$，第二行是序列$\{a_0, a_1, \cdots, a_{n - 1}\}$。数据保证序列$a$可以由至少一个 1 到$n$的排列得到。

输出格式

输出包含一行，表示 Bob 能得到的最高分数。

样例

样例输入 1

4
1 2 2 3

样例输出 1

5

样例输入 2

4
1 1 2 3

样例输出 2

5

数据范围

• 对于 30% 的数据，$N \leq 1000$。
• 对于 100% 的数据，$N \leq 10^5$。