Arithmetic Progressions

All submissions for this problem are available.
Given N integers A_{1}, A_{2}, …. A_{N}, Dexter wants to know how many ways he can choose three numbers such that they are three consecutive terms of an arithmetic progression.
Meaning that, how many triplets (i, j, k) are there such that 1 ≤ i < j < k ≤ N and A_{j}  A_{i} = A_{k}  A_{j}.
So the triplets (2, 5, 8), (10, 8, 6), (3, 3, 3) are valid as they are three consecutive terms of an arithmetic
progression. But the triplets (2, 5, 7), (10, 6, 8) are not.
Input
First line of the input contains an integer N (3 ≤ N ≤ 100000). Then the following line contains N space separated integers A_{1}, A_{2}, …, A_{N} 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.
Example
Input: 10 3 5 3 6 3 4 10 4 5 2 Output: 9
Explanation
The followings are all 9 ways to choose a triplet
1 : (i, j, k) = (1, 3, 5), (A_{i}, A_{j}, A_{k}) = (3, 3, 3) 2 : (i, j, k) = (1, 6, 9), (A_{i}, A_{j}, A_{k}) = (3, 4, 5) 3 : (i, j, k) = (1, 8, 9), (A_{i}, A_{j}, A_{k}) = (3, 4, 5) 4 : (i, j, k) = (3, 6, 9), (A_{i}, A_{j}, A_{k}) = (3, 4, 5) 5 : (i, j, k) = (3, 8, 9), (A_{i}, A_{j}, A_{k}) = (3, 4, 5) 6 : (i, j, k) = (4, 6, 10), (A_{i}, A_{j}, A_{k}) = (6, 4, 2) 7 : (i, j, k) = (4, 8, 10), (A_{i}, A_{j}, A_{k}) = (6, 4, 2) 8 : (i, j, k) = (5, 6, 9), (A_{i}, A_{j}, A_{k}) = (3, 4, 5) 9 : (i, j, k) = (5, 8, 9), (A_{i}, A_{j}, A_{k}) = (3, 4, 5)
Author:  rustinpiece 
Tester:  laycurse 
Editorial  http://discuss.codechef.com/problems/COUNTARI 
Tags  fft, hard, maths, nov12, rustinpiece 
Date Added:  25102012 
Time Limit:  3 sec 
Source Limit:  50000 Bytes 
Languages:  C, JAVA, CS2, PAS fpc, PAS gpc, GO, NODEJS, HASK, D, PERL, FORT, ADA, CAML, ICK, BF, ASM, CLPS, ICON, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, JS, ERL, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions