题目名称是吸引你点进来的。
从前有 个方格排成一行。从左至右依次编号为 。
有一天思考熊想给这 个方格染上黑白两色。
第 个方格上有 个属性：。
如果方格 染成黑色就会获得 的好看度。
如果方格 染成白色就会获得 的好看度。
但是太多了黑色就不好看了。
如果方格 是黑色，并且存在一个白色方格 使得：
那么方格 就被称为奇怪的方格。
如果方格 是奇怪的方格，就会使总好看度减少 。
也就是说对于一个染色方案，好看度为：
方格为黑色方格为白色方格为奇怪的方格
现在给你 ，问所有染色方案中最大的好看度是多少。
第一行一个正整数 。
接下来 行中第 行有用空格隔开的 个非负整数以此表示 。
一个非负整数表示所有染色方案中最大的好看度。
10 0 1 7 3 9 2 7 4 0 9 10 5 1 0 4 2 10 2 7 9 1 5 7 2 6 3 5 3 6 2 6 6 4 1 8 1 6 1 6 0 6 5 2 2 5 0 9 3 5 1 3 0 2 5 5 6 7 1 1 2
55
最优染色方案为：白黑白黑白黑白白白白。
可以发现只有方格 为奇怪的方格。
所以好看度为：。
设 为 中的最大值， 为 中的最大值， 为 中的最大值。对于各个测试点：
每个测试点时间限制：
每个测试点内存限制：
