题目描述

DengDuck 最近痴迷地爱上了区间，各种毒瘤维护让他痴迷，虽然仅仅是痴迷而没有做出来……。

由于你一不小心惹怒了 DengDuck，DengDuck 让你做一道题，做不出来你就寄了。

给你一个长度为 $n$ 的数组 $A$，还有一个常数 $k$。

DengDuck 定义「有意思区间」为满足区间和小于等于 $k$ 的区间。

接下来，DengDuck 为了刁难你，给出了 $q$ 次查询。

每次查询给出 $L,R(1\leq L\leq R\leq n)$，求有多少二元组 $(l,r)$ 满足 $[l,r]$ 是一个「有意思区间」，$L\leq l\leq r\leq R$。

你一定要做出来这道题，薄纱 DengDuck 啊！

输入格式

第一行给出两个正整数 $n,q,k$。

第二行 $n$ 个 整数，分别表示 $A_1,A_2,\cdots,A_n$。

第三行至第 $q+2$，每行两个正整数 $L,R$ 表示一个询问。

输出格式

输出一共 $q$ 行，第 $i$ 行表示第 $i$ 次询问的答案。

5 5 4
1 2 3 4 5
2 3
1 4
1 3
4 5
1 5

2
5
4
1
5

提示

对于 $10\%$ 的数据，$1\leq n,q\leq 100$。

对于 $30\%$ 的数据，$1\leq n,q\leq 3\times10^3$。

对于另外的 $20\%$ 的数据，保证 $A_i=1$，在这 $20\%$ 的数据中，有一半的数据点满足 $n<k$。

对于 $100\%$ 的数据，$1\leq n,q\leq 3\times10^5$，$0\leq A_i\leq 10^9$，$0\leq k\leq 10^9$。