题目背景

这是原问题的另一个版本，在时间限制，数据范围，和部分题面有所不同。

题目描述

诺艾儿是出身于正统精灵的炼金术师的家系中分出的柯涅尔家族的后裔，是精灵、人类和兽人的混血，面对危险的世界，她需要提升自己能力，具体来说，她需要试炼。

试炼的地方可以简化成 $n$ 个区域，每个区域有编号为 $a_i$ 的魔族出没，同时它的危险等级恰好是他的编号。

需要注意的是 $a_i=a_j$ 说明这是同一只魔族，只是在不同位置出现。

诺艾儿会进行 $q$ 次试炼，每次试炼最多攻击 $k$ 个魔族，一次试炼诺艾儿会从 $l$ 出发，前往 $r$ 并传送回家。

诺艾儿会依次遇到 $l$ 到 $r$ 位置的魔族，每遇到一个魔族 $a_i$，诺艾儿可以选择：

1. 不打它。
2. 打它，并且同时满足：
   • 已经打的魔族数目不足 $k$。
   • 不存在 $j\in[l,i),a_j < a_i$ 满足 $a_j$ 还活着。

一个怪物活着当且仅当它没被打。

注意到诺艾儿有很多打魔族的方案，你需要回答这次试炼中可能成为诺艾儿的攻击目标的魔族有多少个。

输入格式

第一行三个正整数 $n,k,q$ 表示试炼之地可划分成的区域数目，一次试炼最多攻击多少个魔族，一共进行多少次试炼。

第二行 $n$ 个正整数，第 $i$ 个正整数 $a_i\ (1\le a_i \le n)$ 表示在 $i$ 位置哪个魔族会出没。

接下来 $q$ 行，每行两个正整数 $l,r\ (1\le l\le r \le n)$，表示一次试炼是从 $l$ 到 $r$ 进行。

输出格式

输出 $q$ 行，第 $i$ 行表示对于第 $i$ 次试炼的答案。

10 3 10
5 4 6 1 8 6 4 2 1 4 
7 9
1 7
3 8
10 10
5 5
4 5
7 9
2 10
1 10
4 4

3
4
5
1
1
2
3
4
5
1

提示

子任务编号	$n\le$	$q\le$	特殊性质	分值	时间限制
$0$	$4000$	$4000$	无	$5$	1.5s
$1$	$10^5$		$a$ 是一个排列	$25$
$2$			$k\le 20$	$20$
$3$			$a_i\le 100$
$4$	$2\times 10^5$	$10^6$	无	$30$

对于 $100\%$ 的数据，满足 $1\le k\le n\le 2\times 10^5,1\le q\le 10^6,1\le a_i \le n$；