#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.