John Doe 有一个弯曲的栅栏,由 n 个矩形木板组成,从左到右排列:第 i (1 ≤ i ≤ n)(从左到右)的木板宽度为 1,高度为 hi。我们假设第 i 个 (1 ≤ i ≤ n)(从左到右)的木板的索引为 i。
从 l 到 r (1 ≤ l ≤ r ≤ n) 的一段栅栏是一系列索引为 l 到 r 的木板,即索引为 l、l + 1、...、r 的木板。从 l 到 r 的栅栏宽度为 r - l + 1。
如果满足以下条件,则从 l1 到 r1 和从 l2 到 r2 的两块栅栏称为匹配:
- 这些碎片不相交,也就是说,没有一块木板,因此它出现在栅栏的两个碎片中;
- 碎片宽度相同;
- 对于所有 i (0 ≤ i ≤ r1 - l1),以下条件成立:hl1 + i + hl2 + i = hl1 + hl2。
约翰选择了几块栅栏,现在想知道每块栅栏有多少个不同的匹配块。如果有一块木板属于其中一块而不属于另一块,则两块栅栏是不同的。
输入
第一行包含整数 n (1 ≤ n ≤ 105) — 栅栏中的木板数量。第二行包含 n 个空格分隔的整数 h1, h2, ..., hn (1 ≤ hi ≤ 109) — 栅栏板的高度。
第三行包含整数 q (1 ≤ q ≤ 105) — 查询数。接下来的 q 行包含两个空格分隔的整数 li 和 ri (1 ≤ li ≤ ri ≤ n) — 第 i 块栅栏的边界。
输出
对于单行上的每个查询,打印一个整数 - 与给定的栅栏匹配的栅栏块数。按顺序打印查询的答案,其中查询在输入中给出。
示例
输入 #1
10 1 2 2 1 100 99 99 100 100 100 6 1 4 1 2 3 4 1 5 9 10 10 10
输出 #1
1 2 2 0 2 9