伐木机不要石头！！！(hard version)
题号：NC271009
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

本题有对应的easy version，区别仅在多次询问中。保证easy version的测试用例集是hard version的真子集，通过困难版本的代码经过简单修改可直接通过简单版本。



看着家里贫瘠的资源，是时候出发采点木头了！

可你突然发现家里没石头，连伐木机都造不好……于是，可露希尔替你发明了无敌手斧，只要木头！可是他的耐久度只有 1，使用完该手斧砍伐掉一棵树之后，该手斧将损坏无法继续使用，也就是一个无敌手斧只能砍一棵树。

现在你已经拥有了大量的无敌手斧，信心百倍的进入了林区。

你面前是 n 棵排成一列的树，每棵树的坚硬程度为 a_i，第一棵树的位置位于 1 号点，第二棵位于 2 号依次类推，直到第 n 棵树。

而你背包里的无敌手斧有 m 个，每个的破坏程度为 b_j，当一个无敌手斧的破坏程度不小于一棵树的坚硬程度时，无敌手斧可以将这棵树砍倒，砍倒后你就可以拿走这棵树的木材。

那聪明的博士就会想了：如果博士想使用无敌手斧砍伐位置在 l 到 r 这段区域内的树木，最多可以带走多少棵树的木材呢？

输入描述:

第一行输入三个数 n，m，q，分别表示树的棵数，无敌手斧的个数和询问次数。

第二行输入 n 个数 a_i， 表示第 i 棵树的坚硬程度。

第三行输入 m 个数 b_j，表示第 j 个无敌手斧的破坏程度。

随后 q 行，每行输入两个数 l，r，表示查询在 [l,r] 中可以砍多少棵树。

数据保证 1 \leq n,m,q \leq 2 \times 10^5，1 \leq a_i \leq 10^9,1 \leq b_j \leq10^9,1\leq l \leq r \leq n。

输出描述:

共输出 q 行，每行一个非负整数，代表对应询问内可拿走多少棵树的木材。
示例1

输入

复制 
5 5 1
1 2 3 4 5
1 1 4 4 5
1 5

输出

复制 
4

说明

对于区间 [1,5] 而言：

第 1 棵树可以匹配上第 1 个手斧。

第 2 棵树可以匹配上第 3 个手斧。

第 4 棵树可以匹配上第 4 个手斧。

第 5 棵树可以匹配上第 5 个手斧。

所以答案为 4。
示例2

输入

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

输出

复制 
5
4
5
5
4
3
2
3
5
4