You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Problem Description

每一年的秋天，提瓦特大陆都会迎来一个非常隆重的聚会， 芙宁娜生日会

又到一年一度芙宁娜的生日庆典，来自崩坏世界的大黑塔女士送给了芙宁娜一个0721号黑塔bot“究极无敌可爱小蛋糕自动生成机”，

这个“究极无敌可爱小蛋糕自动生成机”每一秒可以自动生成一个口味的小蛋糕。

芙宁娜希望将生成的小蛋糕分给旅行者，那位莱特和派蒙三个人。

芙宁娜总共有k秒时间，分配蛋糕的方式为

将第{${1--i}$}秒产生的小蛋糕分给旅行者，

将第{$(i+1)--j$}秒产生的小蛋糕分给那位莱特，

将{$(j+1)--k$}秒产生的小蛋糕分给派蒙。

我们定义每个人收到蛋糕之后会有一个开心值，这个开心值等于收到蛋糕的口味数，

芙宁娜需要准备生日庆典的其他事宜，想不到如何分配蛋糕才能使得三个人总共的开心值最大，希望正在参加重邮acm校赛的您可以帮助她。

形式化的说：你需要将一个长度为 $k$ 的数组 $a$ 分成三段，每一段的值为这一段口味数的种数，求三段之和的最大值。

Input Format

第一行输入一个数字$k（k<1e5）$表示总共的秒数

第二行输入k个数字 $a[i] (a[i]<1e6)$表示每秒机器产生的小蛋糕的口味

Output Format

输出一个数字ans表示三个人的开心值之和的最大值

Sample

输入 #1

5

3 1 4 1 5

输出 #1

5

输入 #2

10

2 5 6 4 4 1 1 3 1 4

输出 #1

9

Hint

样例1中，{3，1}，{4，1}，{5}为最大的分法，开心值$=2+2+1$。