P1013锦鲤（fish）

【题目背景】

特西荼亚海上，有一片神秘的鱼群。这些鱼通体金白，传闻中是祥瑞之兆，于是，世人很喜欢在那片鱼群所在地泛舟航行。

【题目描述】

这片鱼群总是呈现一字型排列，在 Ehundategh 到达这里时，恰好有 $n$ 条鱼，用 $1\sim n$ 编号。Ehundategh 根据每条鱼的外貌形态，给每条鱼分配了一个祥瑞值 $w_i$。

Ehundategh 缓缓行过这些鱼的旁侧，在某个时刻，所有鱼突然高高跃起，Ehundategh 灵光乍现，他想，对于一片连续的鱼群，也就是编号在 $[l,r]$ 中的所有鱼，必然有一个祥瑞值最小的鱼，不妨记这条鱼祥瑞值最小的鱼的祥瑞值为 $f(l,r)$，同时，这所有鱼的祥瑞值之和为 $g(l,r)$。此时，他规定，对于给定的参数 $k$，若成立 $g(l,r)\leq kf(l,r)$，那么称 $[l,r]$ 中所有鱼在参数 $k$ 下形成了献瑞鱼团。

但 Ehundategh 总是摇摆不决的，他不希望所有的鱼都参与构成献瑞鱼团，但他早早计算好了决定鱼团属性的参数 $k$。同时，他认为献瑞鱼团越大越好，于是，他准备了 $q$ 个询问，每次询问给定两个正整数 $l,r$，表示若要求 $[l,r]$ 中所有鱼都参与构成献瑞鱼团，也就是说，在 $[l,r]$ 中的每条鱼都要被划分到恰好一个献瑞鱼团中，最少要划分成多少个不同的献瑞鱼团。

【输入格式】

从文件 $\textbf{\textit{fish.in}}$ 中读入数据。

第一行三个正整数 $n,q,k$，表示鱼的条数、询问个数以及参数 $k$。

第二行 $n$ 个正整数，其中第 $i$ 个正整数表示第 $i$ 条鱼的祥瑞值 $w_i$。

接下来 $q$ 行，每行两个正整数，表示给定的参数 $l,r$。

【输出格式】

输出到文件 $\textbf{\textit{fish.out}}$ 中。

对于每次询问，输出一行一个正整数，表示最少需要划分出的献瑞鱼团数量。

【样例 1 输入】

18 5 522 2 5 1 1 3 2 231 241 353 664 871 8

【样例 1 输出】

1121324253

【说明/提示】

【样例 1 解释】

对于询问 $[4,8]$，可以划分为 $[4,6]$ 和 $[7,8]$。两段的祥瑞值之和分别为 $5$ 和 $4$，均不超过参数 $k=5$ 与区间最小祥瑞值的乘积，因此答案为 $2$。

【样例 2】

见选手目录下的 $\textbf{\textit{fish/fish2.in}}$ 和 $\textbf{\textit{fish/fish2.ans}}$。

该组样例符合测试点 $1\sim 4$ 的数据范围。

【样例 3】

见选手目录下的 $\textbf{\textit{fish/fish3.in}}$ 和 $\textbf{\textit{fish/fish3.ans}}$。

该组样例符合测试点 $5\sim 8$ 的数据范围。

【样例 4】

见选手目录下的 $\textbf{\textit{fish/fish4.in}}$ 和 $\textbf{\textit{fish/fish4.ans}}$。

该组样例符合测试点 $9\sim 13$ 的数据范围。

【样例 5】

见选手目录下的 $\textbf{\textit{fish/fish5.in}}$ 和 $\textbf{\textit{fish/fish5.ans}}$。

该组样例符合测试点 $14\sim 18$ 的数据范围。

【样例 6】

见选手目录下的 $\textbf{\textit{fish/fish6.in}}$ 和 $\textbf{\textit{fish/fish6.ans}}$。

该组样例符合测试点 $19\sim 25$ 的数据范围。

【数据范围】

对于 $100\%$ 的数据，保证：$1\leq n,q\leq 2\times 10^5$，$1\leq k,w_i\leq 10^9$，$1\leq l\leq r\leq n$。

特殊性质 A：满足 $w_1=w_2=\cdots=w_n$。

特殊性质 B：每次询问的答案不超过 $50$。