Sereja and Arcs
All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Sereja have N points, with coordinates (1, 0), (2, 0), ..., (N, 0). Every point has a color, point with coordinate (i, 0) has color A[i].
Sereja have painted arcs between every pair of points with same color. Formally Sereja painted arc between points (i, 0) and (j, 0) if A[i] = A[j] and i != j, such arc has color A[i]. All the arcs are painted such way that they will reside along the positive quadrant.
Now Sereja wants to know how many pairs of arc with different color intersect?
First line contain integer N. Next line contain integers A, A, ..., A[N].
In single line output answer modulo 1000000007 (10^9 + 7).
- 1 ≤ N ≤ 100000
- 1 ≤ A[i] ≤ 100000
Input: 4 1 2 1 2 Output: 1
|Tags||combinatorics, hard, june14, sereja|
|Time Limit:||5 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.