[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能得到的最高分数

样例 #1

样例输入 #1

4
1 2 2 3

样例输出 #1

5

样例 #2

样例输入 #2

4
1 1 2 3

样例输出 #2

5

提示

数据范围

对于 30% 的数据，N ≤ 1000

对于 100% 的数据，N ≤ 10^5