[TJOI2014] 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_i\}$ 的和，Bob的得分是序列 $\{b_i\}$ 的和。求 Bob 能得到的最高分数。

输入格式

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

输出格式

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

输入输出样例 #1

输入 #1

4
1 2 2 3

输出 #1

5

输入输出样例 #2

输入 #2

4
1 1 2 3

输出 #2

5

说明/提示

数据范围

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

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