该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Count Inversion

Description

Recall the problem of finding the number of inversions. As in the course, we are given a sequence of $n$ numbers $a_1,a_2,⋯,a_n$, and we define an inversion to be a pair $i < j$ such that $a_i>a_j$.

We motivated the problem of counting inversions as a good measure of how different two orderings are. However, one might feel that this measure is too sensitive. Let's call a pair a significant inversion if $i < j$ and $a_i>3a_j$. Give an $O(n \log n)$ algorithm to count the number of significant inversions between two orderings.

The array contains N elements ($1\le N\le 100,000$). All elements are in the range from $1$ to $1,000,000,000$.

Input

The first line contains one integer N, indicating the size of the array. The second line contains N elements in the array.

• 50% test cases guarantee that $N < 1000$.

Output

Output a single integer which is the number of pairs of significant inversions.

Samples

6
13 8 5 3 2 1

6