Description

神犇 panda_dtdyy 数学课上刚学习了圆规的使用，他对圆非常感兴趣。于是用圆规随便画了一个圆，并以顺时针次序随机在圆上取了 N 个点。这 N 个点把圆顺次分为了 N 条弧，且弧长均为正整数。他把这个任意四个能够围成矩形的点，称为一组“黄金点组合”。现依次给出这 N 条弧的弧长，请问，他选的这 N 个点中，有多少组“黄金点组合”。

Input Format

第一行为正整数 N。

接下来一行有 N 个数，按顺时针顺序表示他选的 N 个点将圆分割成的圆弧长度。

Output Format

他随机选择的点中，有多少组“黄金点组合”。

Sample

输入样例#1：

8
1 2 2 3 1 1 3 3

输出样例#1：

3

Hint

样例解释如图：

记 S 为圆弧长度最大值。

对于 30% 的数据，N≤50；

对于 60% 的数据，N≤2000；

对于另外 20% 的数据，S≤2；

对于 100% 的数据，N≤100000,S≤20。