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:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
there should be (Ai, Aj, Ak)
I see the language options
can we get any rough estimate
@n0_id No, it should be (i,
It turns out the judge cases
@dpraveen You can find the
Why is Python missing from
what about the number of test
Small problem..big
@admins: why is the language
No Python :( , why?
I think tests are still weak
why isn't scala in supported
can we use dynamic allocation
Getting runTime(other)
why are the cases for i,j,k
@kunalgaurav18 Because of the
hey python not available or
I am having runtime errors!
i am having runtime error
I too get runtime error.
@admin provide some strong
working for thr given test
Why Python is not supported
What does time given in
@saikrishna173 10 seconds
@anton_lunyov: I would be
Any generic suggestions from
@admin: is there only one
run time error is probably
@harshrv1991 The 50000 bytes
@darth&harsh: My source file
what should be output for