TRIPINV  Mega Inversions
The n^2 upper bound for any sorting algorithm
is easy to obtain: just take two elements
that are misplaced with respect to each other
and swap them. Conrad conceived an algorithm
that proceeds by taking not two, but three misplaced
elements. That is, take three elements
ai > aj > ak with i < j < k and place them in
order ak; aj ; ai. Now if for the original algorithm
the steps are bounded by the maximum number
of inversions n(n1)/2, Conrad is at his wits' end as
to the upper bound for such triples in a given sequence. He asks you to write a program
that counts the number of such triples.
Input
The rst line of the input is the length of the sequence, 1 <= n <= 10^5.
The next line contains the integer sequence a1; a2..an.
You can assume that all ai belongs [1; n].
Output
Output the number of inverted triples.
Example
Input: 4
3 3 2 1 Output: 2
hide comments
striver_79:
20190117 10:37:23
Try this https://codeforces.com/problemset/problem/61/E after solving this. The later can be done using coordination compression. 

eulerkochy:
20181231 17:18:24
Solved using segment trees! :)


jmr99:
20180719 22:13:01
2 BIT :) 

k0walsk1:
20180630 16:58:57
No need for 2 BITS, just use one and clear it. 

Sigma Kappa:
20170816 21:58:11
I was the author of this problem back in 2011. The intended solution is using 2 BIT's, got Accepted with long longs. 

hamzaziadeh:
20161030 18:47:35
EZPZ Last edit: 20171004 01:21:24 

Aditya Bahuguna:
20150204 23:18:35
@Alex Abbas: Check if value added to BIT while updating is long long...I was getting WA because of this :) 

Alex Abbas:
20130216 13:27:03
Please tell me.


aristofanis:
20121204 18:41:14
I think you mean decreasing subsequences. 

Lewin Gan:
20111107 08:28:18
for a more difficult version of this problem, try INCSEQ 
Added by:  Krzysztof Lewko 
Date:  20111005 
Time limit:  0.123s0.643s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Nordic programming contest 