14257 - 2024_IDS_Spring_Quiz1_Baganono Pair
|
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 |
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 pairs (i, j) satisfying i < j and ai > (aj × k). He named these pairs "K - Baganono Pairs" 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 "K - Baganono Pairs" and thus hopes you can write a program to help him.
Input
The first line contains two integers n, k.
The second line contains n integer a1, a2, ... , an, being the elements of array a.
Constraints
- For testcases 1 to 3, 1 ≤ n ≤ 1000
- For testcases 4 to 6, 1 ≤ n ≤ 106
- For all the testcases, 1 ≤ a1, a2, ..., an ≤ 1000, 1 ≤ k ≤ 10
Output
Output the total number of pair described in the description.
Remember to print a ‘\n’ at the end of the output.
Tags