SPOJ.com - Problem ABCDEF

ABCDEF - ABCDEF

#binary-search

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

Submit solution!

hide comments

< Previous 14 15 16 17 18 19 20 21 22 23 24 Next >

	Simón Murillo Gómez: 2012-08-06 20:04:55 Finally! after a thousand tries! hint: You don't need long long for the answer.
	Md. shahinur rahaman: 2012-07-31 00:13:23 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..
	Rohit: 2012-07-11 06:46:03 my O(n^3 log n) giving tle..:(( luka check it out Last edit: 2012-07-11 06:47:35
	killerz: 2012-06-27 14:57:57 atlast AC Dont use long long unnecessrily guys ... cost me too much of TLE Last edit: 2012-06-27 15:01:21
	Gurpreet Singh: 2012-06-17 10:36:52 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
	Tarun Gehlaut: 2012-06-12 17:39:45 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..
	devu: 2012-06-02 16:26:43 can spoj support 2 arrays of size 1000000
	Anuj Arora: 2012-04-11 19:39:02 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.
	Aman: 2012-04-02 05:29:46 More test cases please, the above has been fulfilled still WA .
	Harutyunyan Hrayr: 2012-03-22 16:25:32 Why TLE,my soulution is O(n^4) and all my n=100 tests it runs ~1second ?

Submit solution!

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