[TJOI2014] Alice and Bob

Alice和Bob发明了一个新的游戏。给定一个序列{x0,x1,…,xn-1}。Alice得到一个序列{a0,a1,…,an-1},其中a;表示以x;结尾的最长上升子序列的长度;Bob得到一个序列{b0,b1,…,bn-1},其中bi表示以xi开头的最长下降子序列的长度。 Alice的得分是序列{a0,a1,…,an-1}的和,Bob的得分是{b0,b1,…,bn-1}的和。

输入的第一行是n,第二行是序列{a0,a1,……’,an-1}。数据保证序列a可以由至少一个1到n的排列得到

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

4
1 2 2 3

5

4
1 1 2 3

5

### 数据范围 对于 30% 的数据，N ≤ 1000 对于 100% 的数据，N ≤ 10^5