CF232D Fence

约翰有一个高低不平的栅栏，由 $n$ 块木板横向排列组成。这些木板从左到右依次编号为 $1,2,\cdots,n$，其中第 $i$ 号木板宽为 $1$，高为 $h_i$。 定义“栅栏区间”$[l,r]$ 表示第 $l,l+1,\cdots,r$ 块木板单独拿出来组成的栅栏，其宽度为 $r-l+1$。 对于两个栅栏区间 $[l_1,r_1]$ 和 $[l_2,r_2]$，我们称他们是“契合”的，当且仅当： - 两个区间不相交，即不存在一块木板同时属于两个区间 - 两个区间的宽度相同 - 对于所有满足 $0\le i\le r_i-l_1$ 的 $i$，都有 $h_{l_1+i}+h_{l_2+i}=h_{l_1}+h_{l_2}$。 约翰选出了 $q$ 个栅栏区间。对于每个栅栏区间，他都想知道，有多少个互不相同的栅栏区间和这个栅栏区间是“契合”的。 两个栅栏区间互不相同，当且仅当存在一个栅栏，使得这个栅栏在其中一个栅栏区间中出现而不在另一个中。

第一行一个正整数 $n$，表示栅栏长度。 第二行 $n$ 个正整数，依次表示 $h_1,h_2,\cdots,h_n$。 第三行一个正整数 $q$，表示询问个数。 接下来 $q$ 行，其中的第 $i$ 行包含两个正整数 $l_i,r_i$，表示询问有多少个和栅栏区间 $[l_i,r_i]$ 契合的，互不相同的栅栏区间。

输出 $q$ 行，每行一个正整数，表示对应询问的答案。

$ 1\le n\le 10^{5} $，$ 1\le h_{i}\le 10^{9} $，$ 1\le q\le 10^{5} $，$ 1\le l_{i}\le r_{i}\le n $。