#include <algorithm>
#include <iostream>
#include <map>
#include <stdint.h>
#include <string.h>
#include <utility>
#include <vector>

using namespace std;

int main()
{
	const int max_l = 10000000;
	const int max_sticks = 3000;
	const int max_r = 4;
	
	// Precompute binomial coefficients up to choose 4
	uint64_t bin_coeff[1 + max_sticks][1 + max_r];
	
	for(uint64_t n = 1; n <= max_sticks; n++)
	{
		bin_coeff[n][0] = 1ULL;
		
		for(uint64_t r = 1; r <= ((n < max_r) ? n : max_r); r++)
			bin_coeff[n][r] = (bin_coeff[n][r - 1] * (n - (r - 1))) / r;
	}
	
	int n;
	
	cin >> n;
	
	vector<int> sticks;
	map<int,int> sticks_multiplicity;
	vector<pair<int,int> > sticks_multiplicity_sorted;
	
	vector<int> sticks_multiplicity_array(1 + max_l, 0);
	
	for(int i = 0; i < n; i++)
	{
		int a;
		
		cin >> a;
		
		sticks.push_back(a);
		
		if(sticks_multiplicity.find(a) == sticks_multiplicity.end())
			sticks_multiplicity[a] = 0;
			
		sticks_multiplicity[a]++;
		sticks_multiplicity_array[a]++;
	}
	
	sort(sticks.begin(), sticks.end());
	
	for(auto i = sticks_multiplicity.begin(); i != sticks_multiplicity.end(); i++)
		sticks_multiplicity_sorted.push_back(pair<int,int>(i->first,i->second));
		
	uint64_t count = 0ULL;
	
	// (1,1,1,3) case
	// Need to find sticks of multiplicity >= 3
	vector<pair<int,int> > sticks_multiplicity_3;
	
	for(int i = 0; i < sticks_multiplicity_sorted.size(); i++)
		if(sticks_multiplicity_sorted[i].second >= 3)
			sticks_multiplicity_3.push_back(sticks_multiplicity_sorted[i]);
	
	// a + b + c, 2a + b, 3a
	// Strategy is to hash all possible pairs of integers a + b
	vector<uint64_t> pair_hash(2 * max_l + 1, 0);
	
	pair_hash[sticks[0] + sticks[1]] = 1;
	
	// O(n^2)
	for(int i = 2; i < sticks.size(); i++)
	{
		for(int j = 0; j < sticks_multiplicity_3.size(); j++)
			if(sticks_multiplicity_3[j].first - sticks[i] >= 0)
				count += bin_coeff[sticks_multiplicity_3[j].second][3] * (uint64_t) pair_hash[sticks_multiplicity_3[j].first - sticks[i]];
		
		// Update pair_hash
		for(int j = 0; j < i; j++)
			pair_hash[sticks[i] + sticks[j]]++;
	}
	
	// (1,1,2,2) case
	// Sub-cases: (2a,2a), (2a,b+c), (a+b,a+b) and (a+b,c+d)
	fill(pair_hash.begin(), pair_hash.end(), 0);
	
	vector<uint64_t> &unique_pair_hash = pair_hash;
	
	// Data structures for (a+b,c+d)
	vector<uint64_t> pair_accum(2 * max_l + 1, 0ULL);
	vector<uint64_t> pair_combo(2 * max_l + 1, 0ULL);
	
	for(int i = 0; i < sticks_multiplicity_sorted.size(); i++)
		for(int j = i + 1; j < sticks_multiplicity_sorted.size(); j++)
		{
			// (a+b) data structure
			unique_pair_hash[sticks_multiplicity_sorted[i].first + sticks_multiplicity_sorted[j].first] +=
				sticks_multiplicity_sorted[i].second * sticks_multiplicity_sorted[j].second;
				
			// (a+b,c+d) data structure
			pair_combo[sticks_multiplicity_sorted[i].first + sticks_multiplicity_sorted[j].first] +=
				pair_accum[sticks_multiplicity_sorted[i].first + sticks_multiplicity_sorted[j].first] * 
				sticks_multiplicity_sorted[i].second * sticks_multiplicity_sorted[j].second;
				
			pair_accum[sticks_multiplicity_sorted[i].first + sticks_multiplicity_sorted[j].first] +=
				sticks_multiplicity_sorted[i].second * sticks_multiplicity_sorted[j].second;
		}
	
	vector<pair<int,int> > sticks_multiplicity_2;
	
	for(int i = 0; i < sticks_multiplicity_sorted.size(); i++)
		if(sticks_multiplicity_sorted[i].second >= 2)
		{
			sticks_multiplicity_2.push_back(sticks_multiplicity_sorted[i]);
			
			// (2a,2a)
			if(((sticks_multiplicity_sorted[i].first % 2) == 0) && (sticks_multiplicity_array[sticks_multiplicity_sorted[i].first / 2] >= 4))
				count += bin_coeff[sticks_multiplicity_sorted[i].second][2] * bin_coeff[sticks_multiplicity_array[sticks_multiplicity_sorted[i].first / 2]][4];
				
			// (2a,b+c)
			if(((sticks_multiplicity_sorted[i].first % 2) == 0) && (sticks_multiplicity_array[sticks_multiplicity_sorted[i].first / 2] >= 2))
				count += bin_coeff[sticks_multiplicity_sorted[i].second][2]
					* bin_coeff[sticks_multiplicity_array[sticks_multiplicity_sorted[i].first / 2]][2]
					* (uint64_t) unique_pair_hash[sticks_multiplicity_sorted[i].first];
					
			// (a+b,c+d)
			count += bin_coeff[sticks_multiplicity_sorted[i].second][2] *
				pair_combo[sticks_multiplicity_sorted[i].first];
		}
		
	// (a+b,a+b)
	// a and b must occur at least with a multiplicity of 2
	fill(pair_hash.begin(), pair_hash.end(), 0);
	
	for(int i = 0; i < sticks_multiplicity_2.size(); i++)
		for(int j = i + 1; j < sticks_multiplicity_2.size(); j++)
			unique_pair_hash[sticks_multiplicity_2[i].first + sticks_multiplicity_2[j].first] +=
				bin_coeff[sticks_multiplicity_2[i].second][2] * bin_coeff[sticks_multiplicity_2[j].second][2];
				
	for(int i = 0; i < sticks_multiplicity_2.size(); i++)
		count += bin_coeff[sticks_multiplicity_2[i].second][2] *
			(uint64_t) unique_pair_hash[sticks_multiplicity_2[i].first];
			
	cout << count << endl;
	
	return 0;
}

import java.io.InputStream;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.BitSet;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.stream.Collectors;

public class Solution {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int size = scanner.nextInt();

        long numWays = 0L;

        int[] sticks = new int[size];

        BitSet lengths = new BitSet(size);

        for (int i = 0; i < size; i++) {
            sticks[i] = scanner.nextInt();
            lengths.set(sticks[i]);
        }

        Map<Integer, Long> lengthToCount = Arrays.stream(sticks).boxed().collect(Collectors.groupingBy(i -> i, Collectors.counting()));

        for (int length = lengths.length() - 1; length != -1; length = lengths.previousSetBit(length - 1)) {
            int count = lengthToCount.get(length).intValue();

            if (count > 1) {
                numWays += combinationsOf2(count) * waysToMakeTwoEqualSidesUsingFourSticks(length, lengths, lengthToCount);

                if (count > 2) {
                    numWays += combinationsOf3(count) * waysToMakeLengthWithThreeSticks(length, lengths, lengthToCount);
                }
            }

        }

        System.out.println(numWays);

    }

    private static long waysToMakeTwoEqualSidesUsingFourSticks(int sideLength, BitSet lenghtsBitSet, Map<Integer, Long> lenghtsToCount) {
        long count = 0L;

        List<Long> singlePairCounts = new ArrayList<>();

        for (int i = lenghtsBitSet.previousSetBit(sideLength - 1); i != -1; i = lenghtsBitSet.previousSetBit(i-1)) {

            int j = sideLength - i;

            if (j <= i && lenghtsBitSet.get(j)) {
                long ci = lenghtsToCount.get(i);
                long cj = lenghtsToCount.get(j);
                if (i == j) {
                    count += combinationsOf4(ci);
                    long combs2 = combinationsOf2(ci);
                    count += singlePairCounts.stream().mapToLong(Long::longValue).map(c -> c * combs2).sum();
                    singlePairCounts.add(combs2);
                }
                else {
                    count += combinationsOf2(ci) * combinationsOf2(cj);
                    long combs2 = ci * cj;
                    count += singlePairCounts.stream().mapToLong(Long::longValue).map(c -> c * combs2).sum();
                    singlePairCounts.add(combs2);
                }
            }
        }

        return count;
    }

    private static long waysToMakeLengthWithThreeSticks(int totalLength, BitSet lenghtsBitSet, Map<Integer, Long> lengthsToCount) {
        long count = 0L;
        int halfLength = totalLength / 2;
        for (int i = lenghtsBitSet.previousSetBit(totalLength - 1); i != -1 && i > halfLength; i = lenghtsBitSet.previousSetBit(i-1)) {
            for (int j = lenghtsBitSet.previousSetBit(totalLength - i); j != -1 && j >= (totalLength - i) / 2; j = lenghtsBitSet.previousSetBit(j-1)) {
                int k = totalLength - i - j;

                if (k <= j && lenghtsBitSet.get(k)) {

                    long ci = lengthsToCount.get(i);
                    long cj = lengthsToCount.get(j);

                    if (j == k) {
                        count += ci * combinationsOf2(cj);
                    }
                    else {
                        long ck = lengthsToCount.get(k);
                        count += ci * cj * ck;
                    }
                }
            }
        }

        for (int i = lenghtsBitSet.previousSetBit(halfLength); i != -1; i = lenghtsBitSet.previousSetBit(i-1)) {
            for (int j = lenghtsBitSet.previousSetBit(i); j != -1 && j >= (totalLength - i) / 2; j = lenghtsBitSet.previousSetBit(j-1)) {
                int k = totalLength - i - j;

                if (k <= j && lenghtsBitSet.get(k)) {

                    long ci = lengthsToCount.get(i);
                    long cj = lengthsToCount.get(j);
                    long ck = lengthsToCount.get(k);

                    if (i == j && i == k) {
                        count += combinationsOf3(ci);
                    }
                    else if (i == j) {
                        count += combinationsOf2(ci) * ck;
                    }
                    else if (j == k) {
                        count += ci * combinationsOf2(cj);
                    }
                    else {
                        count += ci * cj * ck;
                    }
                }
            }
        }

        return count;
    }


    private static long combinationsOf4(long n) {
        return (n * (n-1) * (n-2) * (n-3)) / 24;
    }

    private static long combinationsOf3(long n) {
        return (n * (n-1) * (n-2)) / 6;
    }

    private static long combinationsOf2(long n) {
        return (n * (n-1)) / 2;
    }
}
 

#!/bin/python3

import math
import os
import random
import re
import sys
import collections

def choose(n,k):
    if k>n:
        return 0
    k = min(k, n-k)
    num,den = 1,1 
    for i in range(k):
        num *= (n-i)
        den *= i+1
    return num//den

def squareCount(l):
    counter = collections.Counter(l)
    l = tuple(counter.keys())
    choose2 = collections.Counter()
    choose3 = collections.Counter()
    choose4 = collections.Counter()
    le = len(l)
    for n in counter:
        count = counter[n]
        if count >= 2:
            choose2[n] = choose(count,2)
            if count >= 3:
                choose3[n] = choose(count,3)
                if count>=4:
                    choose4[n] = choose(count,4)
    ###a+b = c+d
    #t1 all same
    t1 = 0
    #t2 two identical pairs
    t2 = 0
    for i in range(le):
        #all same
        if counter[2*l[i]] >= 2 and counter[l[i]] >= 4:
            t1 += choose4[l[i]]*choose2[2*l[i]]
        if counter[l[i]]>=2:
            for j in range(i+1,le):
                if counter[l[j]]>=2 and counter[l[i]+l[j]] >= 2:
                    t2 += choose2[l[i]]*choose2[l[j]]*choose2[l[i]+l[j]]
                    #two identical pairs
                    
    #doubles for each relevent sum
    doubles = collections.Counter()
    for i in range(le):
        if counter[l[i]] >= 2 and counter[2*l[i]] >= 2:
            doubles[2*l[i]] = choose2[l[i]]

    #pairs Pairs for each relevant sum
    #mpairs Matching pairs for each relevant sum 
    pairs = collections.Counter()
    mpairs = collections.Counter()
    for i in range(le):
        for j in range(i+1,le):
            if counter[l[i]+l[j]] >= 2:
                pairs[l[i]+l[j]] += counter[l[i]]*counter[l[j]]
                mpairs[l[i]+l[j]] += counter[l[i]]**2*counter[l[j]]**2

    #t3: a pair and a double
    t3 = sum(pairs[s]*doubles[s]*choose2[s] for s in doubles if s in pairs)

    #t4: all different
    t4 = sum((pairs[s]**2 - mpairs[s])*choose2[s] for s in pairs)//2


    ###a + b = d-c
    CD = collections.Counter()
    for d in range(le):
        if counter[l[d]]>=3:
            for c in range(le):
                if l[c] < l[d]:
                    CD[l[d]-l[c]] += choose3[l[d]]*counter[l[c]]

    #s1 - a not b possibly one equal to c
    s1 = 0
    
    #s2 - a not b, b equal to c
    s2 = 0

    #s4 two same
    s4 = 0
    
    for a in range(le):
        for b in range(a+1,le):
            s1 += 2*CD[l[a]+l[b]]*counter[l[a]]*counter[l[b]]
            if counter[l[a] + 2*l[b]] >= 3:
                s2 += 2*choose3[l[a] + 2*l[b]]*counter[l[a]]*counter[l[b]]**2
            if counter[2*l[a] + l[b]] >= 3:
                s2 += 2*choose3[2*l[a] + l[b]]*counter[l[b]]*counter[l[a]]**2
            if counter[l[b]] >= 2 and counter[l[a] + 2*l[b]] >= 3:
                s4 += counter[l[a]]*choose2[l[b]]*choose3[l[a]+2*l[b]]
            if counter[l[a]] >= 2 and counter[2*l[a] + l[b]] >= 3:
                s4 += counter[l[b]]*choose2[l[a]]*choose3[2*l[a]+l[b]]

    #s - distinct triples
    s = (s1 - s2)//6

    #s3 - all same
    s3 = 0
    for a in range(le):
        if counter[l[a]] >= 3 and counter[3*l[a]]>=3:
            s3 += choose3[l[a]]*choose3[3*l[a]]
            
            
    return t1 + t2 + t3 + t4 + s + s3 + s4


if __name__ == '__main__':
    n = int(input())

    l = list(map(int, input().rstrip().split()))

    print(squareCount(l))
    

#!/bin/python
from collections import Counter
n = int(raw_input().strip())  # Number of sticks
l = Counter(map(int,raw_input().strip().split(' ')))  # Sticks, length counts
u = l.keys()  # Unique lengths
u.sort()
d = dict([])  # Strictly ways to combine two actual sticks into 'virtual' stick length

for i in xrange(len(u)):
    if l[u[i]] > 1:
        virtual_stick_length = 2 * u[i]
        if virtual_stick_length not in d: d[virtual_stick_length] = set([])
        d[virtual_stick_length].add(i)
    for j in xrange(i+1, len(u)):
        virtual_stick_length = u[i] + u[j]
        if virtual_stick_length not in d: d[virtual_stick_length] = set([])
        d[virtual_stick_length].add(i)

from math import factorial as fcr

square_ways = 0
for i in xrange(len(u)-1, -1, -1):
    length = u[i]
    length_count = l[length]
    if length_count < 2: continue
    
    ways_choose_two_pairs = 0
    if length in d:
        ways_choose_two_of_length = fcr(length_count)/fcr(length_count-2)/fcr(2)
        
        choosing_from = []
        for index in d[length]:
            assert(u[index] in l)
            diff_len = length - u[index]
            assert(diff_len in l)
            diff_len_count = l[diff_len]
            index_count = l[u[index]]
            # print '2(', ways_choose_two_of_length, ')', length, '=', u[index],
            # print '+', diff_len, '(', index_count, ') x (', diff_len_count, ')'
            if diff_len == u[index]:
                if diff_len_count > 3:
                    ways_choose_two_pairs += fcr(diff_len_count)/fcr(diff_len_count-4)/fcr(4)
                choose_two_from_this = fcr(diff_len_count)/fcr(diff_len_count-2)/fcr(2)
                for choice in choosing_from:
                    if len(choice) == 1:
                        prod = fcr(choice[0])/fcr(choice[0]-2)/fcr(2)
                    else:
                        prod = choice[0] * choice[1]
                    ways_choose_two_pairs += choose_two_from_this * prod
                choosing_from.append([diff_len_count])
            else:
                if diff_len_count > 1 and index_count > 1:
                    ways_choose_two_pairs += fcr(diff_len_count)/fcr(diff_len_count-2)/fcr(2) * \
                        fcr(index_count)/fcr(index_count-2)/fcr(2)
                this_prod = diff_len_count * index_count
                for choice in choosing_from:
                    if len(choice) == 1:
                        prod = fcr(choice[0])/fcr(choice[0]-2)/fcr(2)
                    else:
                        prod = choice[0] * choice[1]
                    ways_choose_two_pairs += this_prod * prod
                choosing_from.append([diff_len_count, index_count])
    
    if ways_choose_two_pairs > 0:
        square_ways += ways_choose_two_of_length * ways_choose_two_pairs
        
        
    if length_count < 3: continue
    ways_choose_three = fcr(length_count)/fcr(length_count-3)/fcr(3)

    for j in xrange(i-1, -1, -1):
        sub_len = u[j]
        sub_len_count = l[sub_len]
        diff_len = length - sub_len
        
        num_three_sum_to_length = 0
        if diff_len == sub_len * 2:
            if sub_len_count > 2:
                num_three_sum_to_length += fcr(sub_len_count)/fcr(sub_len_count-3)/fcr(3)
        
        if diff_len not in d:  # No pair sums to this (diff) length
            continue

        for index in d[diff_len]:
            assert(u[index] in l)
            if u[index] == sub_len: continue
            last_len = diff_len - u[index]
            assert(last_len in l)
            if u[index] < sub_len:
                if u[index] != last_len: continue
            last_len_count = l[last_len]
            index_count = l[u[index]]
            # print '3(', sub_len_count, ')', sub_len, '=', u[index],
            # print '+', last_len, '(', index_count, ') x (', last_len_count, ')'
            if u[index] == last_len:
                num_three_sum_to_length += sub_len_count * fcr(last_len_count)/fcr(last_len_count-2)/fcr(2)
            else:
                num_three_sum_to_length += sub_len_count * last_len_count * index_count

        if num_three_sum_to_length > 0:
            square_ways += ways_choose_three * num_three_sum_to_length
            
print square_ways

#include <stdio.h>
#include <stdlib.h>
long long C(long long n,long long r);
void sort_a(int*a,int*c,int size,int*new_size);
void merge(int*a,int*left_a,int*right_a,int*c,int*left_c,int*right_c,int left_size, int right_size,int*new_size);
int a[3000],c[3000],one[10000000]={0};
long long two[10000000]={0};

int main(){
  int N,M,i,j;
  long long ans=0,t1,t2,a2=0,a3=0;
  scanf("%d",&N);
  for(i=0;i<N;i++){
    scanf("%d",a+i);
    one[a[i]-1]++;
    c[i]=1;
  }
  for(i=0;i<N-1;i++)
    for(j=i+1;j<N;j++)
      if(a[i]+a[j]<=10000000)
        two[a[i]+a[j]-1]++;
  sort_a(a,c,N,&M);
  for(i=0;i<M;i++){
    if(c[i]>1){
      for(j=t1=t2=0;a[j]<=a[i]/2 && j<i;j++)
        if(a[j]*2==a[i]){
          if(c[j]>1)
            t2+=t1*C(c[j],2);
          if(c[j]>3)
            t2+=C(c[j],4);
        }
        else if(one[a[i]-a[j]-1]){
          t2+=t1*one[a[i]-a[j]-1]*c[j];
          if(c[j]>1 && one[a[i]-a[j]-1]>1)
            t2+=C(c[j],2)*C(one[a[i]-a[j]-1],2);
          t1+=one[a[i]-a[j]-1]*c[j];
        }
      ans+=t2*C(c[i],2);
      a2+=t2*C(c[i],2);
    }
    if(c[i]>2){
      for(j=t1=0;j<i;j++)
        if(two[a[i]-a[j]-1]){
          t2=two[a[i]-a[j]-1];
          if(a[j]*3==a[i]){
            if(c[j]>2)
              t1+=C(c[j],3)*6;
            if(c[j]>1)
              t2-=C(c[j],2);
          }
          else if(a[i]-2*a[j]>0 && one[a[i]-2*a[j]-1]){
            if(c[j]>1)
              t1+=C(c[j],2)*one[a[i]-2*a[j]-1]*3;
            t2-=c[j]*one[a[i]-2*a[j]-1];
          }
          if(a[j]*3!=a[i] && (a[i]-a[j])/2*2==a[i]-a[j] && one[(a[i]-a[j])/2-1]>1){
            t1+=c[j]*C(one[(a[i]-a[j])/2-1],2)*3;
            t2-=C(one[(a[i]-a[j])/2-1],2);
          }
          t1+=t2*c[j]*2;
        }
      ans+=t1*C(c[i],3)/6;
      a3+=t1*C(c[i],3)/6;
    }
  }
  printf("%lld",ans);
  //printf("%lld %lld %lld",ans,a2,a3);
  return 0;
}
long long C(long long n,long long r){
  int i;
  long long ans=1;
  for(i=0;i<r;i++)
    ans*=(n-i);
  for(i=2;i<=r;i++)
    ans/=i;
  return ans;
}
void sort_a(int*a,int*c,int size,int*new_size){
  if (size < 2){
    (*new_size)=size;
    return;
  }
  int m = (size+1)/2,i;
  int *left_a,*right_a,*left_c,*right_c;
  left_a=(int*)malloc(m*sizeof(int));
  right_a=(int*)malloc((size-m)*sizeof(int));
  left_c=(int*)malloc(m*sizeof(int));
  right_c=(int*)malloc((size-m)*sizeof(int));
  for(i=0;i<m;i++){
    left_a[i]=a[i];
    left_c[i]=c[i];
  }
  for(i=0;i<size-m;i++){
    right_a[i]=a[i+m];
    right_c[i]=c[i+m];
  }
  int new_l_size=0,new_r_size=0;
  sort_a(left_a,left_c,m,&new_l_size);
  sort_a(right_a,right_c,size-m,&new_r_size);
  merge(a,left_a,right_a,c,left_c,right_c,new_l_size,new_r_size,new_size);
  free(left_a);
  free(right_a);
  free(left_c);
  free(right_c);
  return;
}
void merge(int*a,int*left_a,int*right_a,int*c,int*left_c,int*right_c,int left_size, int right_size,int*new_size){
  int i = 0, j = 0,index=0;
  while (i < left_size|| j < right_size) {
    if (i == left_size) {
      c[index] = right_c[j];
      a[index++] = right_a[j];
      j++;
    } else if (j == right_size) {
      c[index] = left_c[i];
      a[index++] = left_a[i];
      i++;
    } else if (left_a[i] <= right_a[j]) {
      c[index] = left_c[i];
      a[index++] = left_a[i];
      i++;
    } else {
      c[index] = right_c[j];
      a[index++] = right_a[j];
      j++;
    }
    if(index>1&&a[index-2]==a[index-1]){
      c[index-2]+=c[index-1];
      index--;
    }
  }
  (*new_size)=index;
  return;
}