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(n-1)/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 first 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

Added by:Krzysztof Lewko
Date:2011-10-05
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Nordic programming contest

hide comments
2018-12-31 17:18:24
Solved using segment trees! :)
2018-07-19 22:13:01
2 BIT :)
2018-06-30 16:58:57
No need for 2 BITS, just use one and clear it.
2017-08-16 21:58:11 Sigma Kappa
I was the author of this problem back in 2011. The intended solution is using 2 BIT's, got Accepted with long longs.
2016-10-30 18:47:35
EZPZ

Last edit: 2017-10-04 01:21:24
2015-02-04 23:18:35 Aditya Bahuguna
@Alex Abbas: Check if value added to BIT while updating is long long...I was getting WA because of this :)
2013-02-16 13:27:03 Alex Abbas
Please tell me.
y am i getting WA.
Using BIT and long long variables
...
2012-12-04 18:41:14 aristofanis
I think you mean decreasing subsequences.
2011-11-07 08:28:18 Lewin Gan
for a more difficult version of this problem, try INCSEQ
2011-10-15 20:00:06 sri
why am i getting WA? is the result storable in long long int in c???
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.