A slope sensor logs n snow-depth readings in time order (values may be negative after correction). A steep drop pair is a pair of positions (i, j) with i < j where the earlier reading is more than double the later one, that is depth[i] > 2 * depth[j].
Count the number of steep drop pairs. The intended approach counts these pairs during a merge sort: when merging two sorted halves, for each value in the left half advance a pointer over the right half to tally how many later readings it more than doubles.
Input format
Line 1: an integer n, the number of readings.
Line 2: n space-separated integers, the readings in time order.
Output format
A single integer: the number of steep drop pairs.
Constraints
- 1 <= n <= 100000
- -1000000000 <= each reading <= 1000000000