14256 - 2024_IDS_Spring_Assignment1_Baganono Tuple
|
Time |
Memory |
| Case 1 |
1 sec |
256 MB |
| Case 2 |
1 sec |
256 MB |
| Case 3 |
1 sec |
256 MB |
| Case 4 |
1 sec |
256 MB |
| Case 5 |
1 sec |
256 MB |
| Case 6 |
1 sec |
256 MB |
| Case 7 |
1 sec |
256 MB |
| Case 8 |
1 sec |
256 MB |
| Case 9 |
1 sec |
256 MB |
| Case 10 |
1 sec |
256 MB |
Description
Chyen is an mathematician, we usually call him as "Baganono" to signify his intelligence.
One day, Chyen discovered that within a sequence of length N, there are many tuples (i, j, k) satisfying i < j < k and ai < aj < ak. He named these tuples "Baganono Tuples" and was very excited about his discovery.
However, due to the length of the sequence is too long, he was unable to count the total number of Baganono Tuples and thus hopes you can write a program to help him.
Input
The first line contains an integer n, being the size of array. The second line contains n integer a1, a2, ... , an, being the elements of array a.
Constraints
- For testcases 1 to 3, 1 ≤ n ≤ 100
- For testcase 4 to 6, 1 ≤ n ≤ 3000
- For testcases 7 to 10, 1 ≤ n ≤ 106
- For all the testcases, 1 ≤ ai ≤ n, ∀ 1 ≤ i ≤ n, and all the elements in a are distinct
Output
Output the total number of tuple described in the description.
Remember to print a ‘\n’ at the end of the output.
Tags