时空限制

1S/512M

题目描述

汗水浇灌的跑道不会说话，但时间会给出回答。

某市举办了一场马拉松比赛，共有 $n$ 位选手完成比赛，他们的最终成绩均以整数秒为单位记录。第 $i$ 位选手的成绩为 $t_i$。

为了对比赛成绩进行分层统计，主办方设置了 $q$ 个查询。每个查询给定一个时间区间 $[l_i, r_i]$，你需要统计所有成绩落在该区间内的选手成绩所对应的“合理值”$^{\dagger}$。若该区间内不存在任何选手成绩，则输出 $0$。

$^{\dagger}$ 对于一次查询给定的时间区间 $[l, r]$，设所有满足 $l \le t_i \le r$ 的成绩按任意顺序组成数组

其中 $m$ 表示满足条件的成绩个数。那么该查询的“合理值”定义为

格式

输入格式

第一行包含两个正整数 $n, q$，分别表示参赛选手的数量和查询次数。

第二行包含 $n$ 个非负整数 $t_1, t_2, \dots, t_n$，依次表示每位选手的完赛时间。

接下来的 $q$ 行，每行包含两个非负整数 $l_i, r_i$，表示一次查询的时间区间。

输出格式

输出 $q$ 行，每行一个整数表示该询问的合理值。

样例

样例输入 #1

6 4
3 1 4 1 5 9
1 9
2 6
0 0
4 9

样例输出 #1

93
14
0
26

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

对于 $100\%$ 的数据，保证 $1\le n,q\le 2 \times 10^5,0\le t_i,l_i,r_i\le 10^4,l_i\le r_i$。