庆祝新年,很多人发布多米诺骨牌倒下的视频;以下是其中的列表:https://www.youtube.com/results?search_query=New+Years+Dominos
生活在 2D 世界中的用户 ainta 也将发布一段视频。
二维笛卡尔平面上有 n 个多米诺骨牌。第 i 个多米诺骨牌 (1 ≤ i ≤ n) 可以表示为平行于 y 轴、长度为 li 的线段。多米诺骨牌的最低点位于 x 轴上。我们将第 i 个多米诺骨牌的 x 坐标表示为 pi。多米诺骨牌是一个接一个地放置的,因此 p1 < p2 < ... < pn - 1 < pn 成立。
用户 ainta 想要拍摄多米诺骨牌倒下的视频。为了让多米诺骨牌倒下,他可以将单张多米诺骨牌推到右边。然后,多米诺骨牌会倒下,画出一个圆形的轨道,直到线段与x轴完全重叠。
另外,如果第 s 张多米诺骨牌在倒下时碰到了第 t 张多米诺骨牌,则第 t 张多米诺骨牌也会向右倒下,过程与上述相同。当且仅当表示 s 和 t 的线段相交时,多米诺骨牌 s 才会触及多米诺骨牌 t。
参见上图。如果他将最左边的多米诺骨牌推到右边,它就会倒下,接触到多米诺骨牌 (A)、(B) 和 (C)。结果,多米诺骨牌(A)、(B)、(C)也会向右倒下。然而,多米诺骨牌(D)不会因为推动最左边的多米诺骨牌而受到影响,但最终它会因为第一次被多米诺骨牌(C)接触而倒下。
上图是倒下的多米诺骨牌的例子。每个红色圆圈表示两个多米诺骨牌的碰触。
用户 ainta 有 q 个发布视频的计划。第 j 个多米诺骨牌从推动第 xj 个多米诺骨牌开始,一直持续到第 yj 个多米诺骨牌倒下。但有时候,这样的计划可能无法实现,所以他不得不加长一些多米诺骨牌。将单个多米诺骨牌的长度增加 1 需要花费 1 美元。用户 ainta 想知道对于每个计划,实现它所需的最低成本。计划是独立处理的,即。 e.如果在某些计划中增加多米诺骨牌的长度,则不会影响其在其他计划中的长度。除了第 xj 个多米诺骨牌和第 yj 个多米诺骨牌之外,将倒下的一组多米诺骨牌并不重要,但最初的推动应该在多米诺骨牌 xj 上。
输入
第一行包含一个整数 n (2 ≤ n ≤ 2 × 105)——多米诺骨牌的数量。
接下来的 n 行描述了多米诺骨牌。第 i 行 (1 ≤ i ≤ n) 包含两个空格分隔的整数 pi, li (1 ≤ pi, li ≤ 109) — 第 i 块多米诺骨牌的 x 坐标和长度。保证 p1 < p2 < ... < pn - 1 < pn。
下一行包含一个整数 q (1 ≤ q ≤ 2 × 105) — 计划数量。
接下来 q 行描述了计划。第 j 行 (1 ≤ j ≤ q) 包含两个空格分隔的整数 xj, yj (1 ≤ xj < yj ≤ n)。这意味着第j个计划是,推动第xj张多米诺骨牌,并拍摄视频,直到第yj张多米诺骨牌倒下。
输出
对于每个计划,打印一行包含实现该计划所需的最低成本。如果不需要成本,则打印 0。
示例
输入 #1
6 1 5 3 3 4 4 9 2 10 1 12 1 4 1 2 2 4 2 5 2 6
输出 #1
0 1 1 2
注意
考虑这个例子。多米诺骨牌的摆放方式如下图所示。
我们来看看第四个方案。要通过推动第二张多米诺骨牌使第六张多米诺骨牌倒下,第三张多米诺骨牌(其x坐标为4)的长度应增加1,第五张多米诺骨牌(其x坐标为9)应增加1(其他选择是将第四张多米诺骨牌而不是第五张多米诺骨牌也增加1)。然后,多米诺骨牌就会倒下,如下图所示。每个十字表示两个多米诺骨牌之间的接触。