Description

lily最近在玩一个整数游戏。在一个圆周上有m个整数，且这m个整数的和大于0，当这个圆周上存在负数时，便进行下面的操作： 选择一个负数Y，把它相邻的两个整数X和Z改成X+Y和Z+Y，然后把这个负数Y改成正数(-Y)。 这个游戏直到圆周上不存在负数时结束。经证明，不论选择怎么样的顺序来操作其中的负数，都在相同步数中结束。lily想在每一次游戏前知道需要多少步结束，以此来检验自己的操作是否正确，当然这需要你编程给他以帮助。

Input

每组数据第一行有一个正整数 m (3<m<100)，下一行有m个[-100,100]范围内的整数。

Output

对于每一组数据，输出一个正整数，表示游戏会在多少步时结束。

Sample

Input

3
1 -1 1
5
1 2 3 4 5

Output

1
0

Source: DK