题目描述

点此下载 2024 年实验室二面题解

在一维我的世界中水只会向左右扩散。一条长度为$n$的直线由$n$个编号为$1,2,3,...,n$的方块组成，在编号为$i$的方块上倒一桶水，水会向左右各扩散$7$格，即区间$[max(1,i-7), min(n,i+7)]$内的方块将变成有水方块。已知有$m$个方块被倒上了水，现有$q$次询问，每次询问区间$[l,r]$内共有多少有水方块。

输入描述

第一行输入3个整数$n,m,q$(分别表示直线长度，倒水方块个数，询问次数)$;$

接下来1行输入$m$个整数$w_{i}$(表示倒水方块的编号)$;$

接下来$q$行每行输入两个整数$l,r$(表示询问的区间)。

$1<=n<=2e6,1<=m,w_{i}<=n,1<=q<=1e4, 1<=l<r<=n$.

输出描述

输出$q$行，每行一个整数表示区间内的有水方块个数。

示例 1

输入

100 5 5
9 18 34 68 81
1 100
3 59
1 18
32 89
77 93

输出

67
38
17
38
12