题目描述

很久以前，在森林里住着两只兔子汤姆和杰瑞。在一个阳光明媚的下午，他们计划用一些石头玩游戏。地面上有$n$块石头，它们按顺时针方向排列。也就是说，第一块石头与第二块石头和第$n$块石头相邻，第二块石头与第一块石头和第三块石头相邻，依此类推。第 $i$个石头的重量为 $a_i$。

兔子从一块石头跳到另一块石头。汤姆总是顺时针跳，而杰瑞总是逆时针跳。

一开始，兔子都选择一块石头并站在上面。然后，在每个转弯处，汤姆都应该选择一块自己没有踩过的石头然后跳到上面，杰里应该做与汤姆相同的事情，但是跳跃方向是逆时针方向。

由于某种未知的原因，任何时候，两只兔子站立的两块石头的重量都应该相等。此外，任何兔子都不能跳过自己踩过的石头。换句话说，如果汤姆站在第二块石头上，它就不能从第一块石头跳到第三块石头，也不能从 $n$ 块石头跳到第四块石头。

请注意，在整个过程中，两只兔子可以同时站在同一块石头上。

现在，他们希望找出遵循最佳策略可以玩的最大回合数。

输入格式

第一行包含一个整数$n$，表示石头的数量。

下一行包含由空格分隔的$n$个整数，第$i$个整数$a_i$表示第$i$个石头的重量。（$1 \le n \le 1000,1 \le a_i \le 1000$）

输出格式

输出一个表示最大圈数的整数

样例

输入

4 
1 1 2 1

4

输出

6 
2 1 1 2 1 3

5

提示

对于第一种情况，汤姆的路径为1、2、3、4，杰瑞的路径为1、4、3、2。

对于第二种情况，汤姆的路径为1,2,3,4,5，杰瑞的路径为4,3,2,1,5。