题目描述

给定 $N$ 个数的序列 $a_1,a_2, \dots ,a_N$ ，定义一个数对 $(a_i, a_j)$ 为 “重要逆序对” 的充要条件为 $i < j$ 且 $a_i > 2 \times a_j$ 。

求给定序列中“重要逆序对”的个数。

输入

本题有多个测试点，每个测试点分为两行：

第一行为序列中数字的个数 $N$ （ $1 ≤ N ≤ 200000$ ）；

第二行为序列 $a_1, a_2, \dots , a_N$ ($0 ≤a_i≤ 10000000$ )，由空格分开。

$N=0$ 表示输入结束。

输出

每个测试点一行，输出一个整数，为给序列中“重要逆序对”的个数。

样例

10
0 9 8 7 6 5 4 3 2 1
0

16

说明

请注意答案范围，如果使用 $printf$ 输出 $long$ $long$ 类型，请用 $\%lld$ 。

来源

电子学会五级