Raghav is good in mathematics. He loves to ask puzzles with his friends. One day, he decides to challenge his friend Aditya who is not good with puzzles. So, Aditya needs your help in determining the solution to the puzzle asked by his friend which is stated as:-

Tell the total number of ways he can choose three numbers from N integers A1, A2, …. AN such that they are three consecutive terms of an arithmetic progression.

Meaning that, how many triplets (i, j, k) are there such that 0 < i < j < k < N+1 and Aj - Ai = Ak - Aj.

So the triplets (1, 5, 9), (2, 2, 2), (7, 4, 1) are valid as they are three consecutive terms of an arithmetic progression. But the triplets (2, 3, 7), (1, 1, 8) are not.

Input

First line of the input contains an integer N (2< N <100001). Then the following line contains N space separated integers A1, A2, …, AN and they have values between 1 and 30000 (inclusive).

Output

Output the number of ways to choose a triplet such that they are three consecutive terms of an arithmetic progression.