题目描述

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

输入

本题有多个测试点，每个测试点分为两行：第一行为序列中数字的个数$N（1 ≤ N ≤ 200000）$，第二行为序列$a_1, a_2 ... 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