2276 - 求逆序对问题

题目描述

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

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

输入

本题有多个测试点,每个测试点分为两行:

第一行为序列中数字的个数 N1 ≤ 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

来源

电子学会五级

标签
题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 0
通过人数 0
金币数量 2 枚
难度 基础


上一题 下一题