P4578.第1题-妖伞传递
题目描述
在一条数轴上有n(1<n<1000)个人，第i个人的出生点为 pi，终点为 qi(1≤pi<qi<109)。所有人的出生点两两不同，且按从小到大的顺序输入(p1<p2<⋅⋅⋅<pn)；对于任意i，都有 pi<qi，即所有人都只会沿数轴正方向移动。
最开始，第1个人持有妖伞，并从自己的出生点p1出发前往终点q1。
移动过程中，所有已加入的人会形成一个队伍，并按照以下规则行动：
加入队伍：当当前持伞队伍经过某个人的出生点pi时，如果此人尚未加入过队伍，则该人立即加入到队伍末尾("经过"包括恰好停在该点的情况)。
离开队伍：当某个人到达自己的终点qi时，该人会立刻离开队伍，并且之后不会再次加入队伍。
妖伞交接：如果离开队伍的人恰好是当前持有妖伞的人，若此时队伍非空，则妖伞交给新的队首;若此时队伍为空，则妖伞会停留在当前位置不动，此后所有尚未加入过队伍的人中，出生点距离妖伞当前位置最近的人会先前往该位置取得妖伞，再继续前往自己的终点。若该人在前往取伞途中经过了其他尚未加入过队伍的人的出生点，这些人同样会按规则加入队伍末尾。
最近人的唯一性：题目保证所有人的出生点互不相同且严格递增，因此当队伍为空时，距离妖伞最近且尚未加入的人是唯一确定的。
定义第i 个人的贡献值为该人持有妖伞期间，妖伞实际发生位移的总距离。请输出每个人的贡献值。
输入描述
第一行输入一个整数 n(1<n<1000)，表示人数。
接下来 n 行，每行输入两个整数 pi,qi(1<pi<qi<109)，表示第 i个人的出生点和终点,满足p1<p2<...<pn。
输出描述
输出一行几个整数，第i个整数表示第i个人持有妖伞期间，妖伞实际发生位移的总距离。
样例1
输入
4
1 10
5 6
9 30
20 25
输出
9 0 20 0
说明
初始时，第1个人在位置1持有妖伞并出发。当队伍移动到位置5时，第2个人加入；当队伍移动到位置9时，第3个人加入；第1个人到达终点10后离开，贡献为10−1=9。
随后第2个人成为新的队首，但其终点6已在当前位置左侧，立刻离队，贡献为0。队伍继续前进，第4个人在位置 20 加入；第4个人到达
终点 25时离队，在此之前未成为持伞者，贡献为0。最终第3个人持有妖伞从位置10移动到终点30，贡献为 30−10=20
