#3947. 重要逆序对

重要逆序对

描述

给定N个数的序列a1,a2,...aN,定义一个数对(ai, aj)为“重要逆序对”的充要条件为 i < j 且 ai > 2aj。求给定序列中“重要逆序对”的个数。

输入

第一行为序列中数字的个数N(1 ≤ N ≤ 200000)。 第二行为序列a1, a2 ... aN(0 ≤a ≤ 10000000),由空格分开。

输出

输出一个整数,为给序列中“重要逆序对”的个数。

样例输入

10 0 9 8 7 6 5 4 3 2 1

样例输出

16

提示

如果使用printf输出long long类型,请用%lld 数据范围 对于40%的数据,有N ≤ 1000。

Limitation

1s, 1024KiB for each test case.