Pusheen is a fat and lazy cat. However, he might occasionally fly around town with his helicopter.
One day, Pusheen realises that that a portion of town is populated with many high-rise buildings, along a straight line. In total, there are N buildings in total, each of them equally spaced 1 unit apart, measured from midpoint to midpoint. In addition, the ith building from the left will have height Hi units.
To past time, Pusheen decides to fly his helicopter there. He will pick a building A and fly to another building B. However, as Pusheen is not very good at flying, he is unable to fly between a pair of buildings if the elevation ratio is more than equal U. The elevation ratio between two buildings is the difference in height divided by the horizontal distance between them. For instance, the elevation ratio between two buildings i and j will be abs(Hi - Hj)/abs(i - j) where abs is the absolute function.
However, flying with a low elevation ratio is also very boring. As such, Pusheen wants to know how many pairs of buildings there are such that their elevation ratio is between L ≤ elevation ratio < U.
To clarify, Pusheen does not consider pair (A, B) and pair (B, A) as two separate pairs, since the buildings and elevation ratio are the same.
The input will consist of 2 lines.
The first line will contain 3 integers, N, L and U.
The second line contain N integers, with the ith integer being Hi.
Output a single integer, the number of pairs of buildings such that their elevation ratio is between L (inclusive) and U (exclusive).
For all testcases, 0 ≤ L < U ≤ 109 and 0 ≤ Hi ≤ 109.
Subtask 1 (27%): 2 ≤ N ≤ 2000.
Subtask 2 (26%): 2 ≤ N ≤ 100000, 0 < U - L ≤ 10.
Subtask 3 (47%): 2 ≤ N ≤ 100000. No further restrictions.
Subtask 4 (0%): Sample Testcase
Sample Testcase 1
6 1 3
8 7 1 2 2 8
The pairs of buildings are (1, 2), (3, 4), (2, 4), (2, 5), (3, 6), (1, 4), (1, 5).