300319: CF61E. Enemy is weak
Memory Limit:256 MB
Time Limit:5 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Enemy is weak
题意翻译
- 给定 $n$ 个数的序列 $a$。您要求出满足 $i<j<k$ 并且 $a_i > a_j > a_k$ 的三元组 $(i,j,k)$ 的个数。 - $3\le n\le 10^6$,$1\le a_i\le 10^9$。题目描述
The Romans have attacked again. This time they are much more than the Persians but Shapur is ready to defeat them. He says: "A lion is never afraid of a hundred sheep". Nevertheless Shapur has to find weaknesses in the Roman army to defeat them. So he gives the army a weakness number. In Shapur's opinion the weakness of an army is equal to the number of triplets $ i,j,k $ such that $ i<j<k $ and $ a_{i}>a_{j}>a_{k} $ where $ a_{x} $ is the power of man standing at position $ x $ . The Roman army has one special trait — powers of all the people in it are distinct. Help Shapur find out how weak the Romans are.输入输出格式
输入格式
The first line of input contains a single number $ n $ ( $ 3<=n<=10^{6} $ ) — the number of men in Roman army. Next line contains $ n $ different positive integers $ a_{i} $ ( $ 1<=i<=n,1<=a_{i}<=10^{9} $ ) — powers of men in the Roman army.
输出格式
A single integer number, the weakness of the Roman army. Please, do not use %lld specificator to read or write 64-bit integers in C++. It is preffered to use cout (also you may use %I64d).
输入输出样例
输入样例 #1
3
3 2 1
输出样例 #1
1
输入样例 #2
3
2 3 1
输出样例 #2
0
输入样例 #3
4
10 8 3 1
输出样例 #3
4
输入样例 #4
4
1 5 4 3
输出样例 #4
1