#SDNU1686. 一维碰撞(困难)

一维碰撞(困难)

Description

和简单版本一样

Format

Input

和简单版本一样

Output

每一行输出一个整数,发生了多少次碰撞

Samples

3
1000000000
100000000
1000000
99345
31415
3141