ABCDEF - ABCDEF

You are given a set S of integers between -30000 and 30000 (inclusive).

Find the total number of sextuples  that satisfy: 

 

Input

The first line contains integer N (1 ≤ N ≤ 100), the size of a set S.

Elements of S are given in the next N lines, one integer per line. Given numbers will be distinct.

Output

Output the total number of plausible sextuples.

Examples

Input:
1
1

Output:
1
Input:
2
2
3

Output:
4
Input:
2
-1
1

Output:
24
Input:
3
5
7
10

Output:
10



Added by:Luka Kalinovcic
Date:2009-07-13
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:own problem

hide comments
2012-08-06 20:04:55 Simón Murillo Gómez
Finally! after a thousand tries!
hint: You don't need long long for the answer.
2012-07-31 00:13:23 Md. shahinur rahaman
binary search is efficient where values would differ most and Size of arrays would differ huge. But here just use O(m+n) optimized search in m and n sizes sorted array.

TLE--(30000*30000 + 30000) < 2^31..So DONT USE LONG LONG because LONG LONG requires 8 bytes where int only 4.

Nice problem really..
2012-07-11 06:46:03 Rohit
my O(n^3 log n) giving tle..:(( luka check it out

Last edit: 2012-07-11 06:47:35
2012-06-27 14:57:57 killerz
atlast AC
Dont use long long unnecessrily guys ... cost me too much of TLE

Last edit: 2012-06-27 15:01:21
2012-06-17 10:36:52 Gurpreet Singh
Simple O(n^4) getting TLE... :-(
Edit : Fun problem !!!
Started with easiest solution of O(n^4) (got TLE),
then reduced to O(n^3 log(n)) using STL (still TLE),
and finally reduced to O(n^3 log(n)) without STL and got AC in 6.6 sec :D...

Last edit: 2012-06-17 11:42:00
2012-06-12 17:39:45 Tarun Gehlaut
Guys i was trying this using BST where the tree has a prop to store frequency of repition of any given number...
this eliminates the problem of grping the terms + gives binary searching...
I m getting TLE though the code runs well till (11) case..
2012-06-02 16:26:43 devu
can spoj support 2 arrays of size 1000000
2012-04-11 19:39:02 Anuj Arora
No need to use binary search, if you know how to do linear comparison of two sorted arrays in an optimized way. Got AC with this :)
Only thing is dont forget to see 'd' cant be zero.
2012-04-02 05:29:46 Aman
More test cases please, the above has been fulfilled still WA .
2012-03-22 16:25:32 Harutyunyan Hrayr
Why TLE,my soulution is O(n^4) and all my n=100 tests it runs ~1second ?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.