题目描述

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_i\}$ 的和，Bob的得分是序列 $\{b_i\}$ 的和。

输入格式

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

输出格式

输出包含一行,表示在序列 $\{a_i\}$ 给定的情况下 Bob 能得到的最高分数。

4
1 2 2 3

5

4
1 1 2 3

5

提示

数据范围

对于 $30\%$ 的数据，$N \le 1000$。

对于 $100\%$ 的数据，$N \le 10^5$。