当前没有测试数据。

题目描述

$\hspace{15pt}$小鸡有一个由 $n$ 个值域为 $[1,m]$ 的正整数构成的数组 $\{a_1,a_2,\dots,a_n\}$，每个元素都是在值域中独立均匀随机生成的。

$\hspace{15pt}$现在他希望你能够回答他的 $q$ 个问题：
$\hspace{15pt}$第 $i$ 个问题包含一个正整数 $k_i$ ，他希望你回答有多少个不同的正整数对 $(l,r)$，满足 $1\leq l \leq r \leq n$ 且 $\max\{a_l,a_{l+1},\dots ,a_r\}$$\times \min\{a_l,a_{l+1},\dots ,a_r\} \ge k_i$。

输入描述

$\hspace{15pt}$第一行输入三个正整数 $n,m,q（1 \leq n,q \leq 10^5；1 \leq m \leq 10^6）$代表数组长度、元素值域、问题个数。 $\hspace{15pt}$第二行输入 $n$ 个正整数 $a_1, a_2, \cdots, a_n\left(1\leq a_i\leq m\right)$ 代表数组元素。保证数据在值域中独立均匀随机生成。
$\hspace{15pt}$此后 $q$ 行，每行输入一个正整数 $k\left(1\leq k \leq 10^{12}\right)$ 代表鸡哥的一个问题。

输入描述

$\hspace{15pt}$对于每个问题，输出一行一个整数，代表满足条件的正整数对 $(l,r)$ 的数量。

输出描述

输入

5 5 3
3 5 2 4 1
10
12
8

输出

7
3
9