题目背景

Source: AMPPZ 2019.

题目描述

你拥有一家非常特别的书店，专门售卖旧书。但你将所有书籍随机排列在单一书架上，并不关心书籍的内容。你的客户也是如此——他们通常走进书店，直接要求“书架上从这本开始到这本结束的所有书”。准确地说，每位客户购买的是书架上某个连续（且非空）的书籍片段。

不过，有时你会遇到更挑剔的客户，他们对书籍有更高的要求——实际上，他们希望书籍的尺寸合适。一位挑剔的客户希望书架上某个连续片段中的所有书籍高度均不小于 $l$ 且不大于 $h$。

给定一个整数序列——书架上所有书籍的高度——请确定满足这些要求的连续片段数量。

另外，我们提到书籍是随机排列的。形式上，输入序列由以下程序生成，其中 $N \in \{1, 2, \ldots, 100000\}$ 且 $M = 10^q$（$q \in \{1, 2, \ldots, 6\}$）：

srand48(N + M);
for (int i = 0; i < N; ++i)
    a[i] = 1 + lrand48() % M;

你实际上无需了解 RAND48 库的工作原理。只需假设函数 lrand48 返回均匀随机生成的 31 位非负整数即可。

输入格式

本题单个测试点内有多组测试数据。

输入的第一行包含测试数据数量 $z$（$1 \leq z \leq 5$）。每组测试数据的格式如下：

• 测试数据的第一行包含书籍数量 $n$ 和挑剔客户数量 $k$（$1 \leq n \leq 200\,000$，$1 \leq k \leq 500\,000$）。
• 第二行包含 $n$ 个不超过 $1\,000\,000$ 的正整数——从左到右所有书籍的高度。
• 接下来的 $k$ 行描述客户的需求。第 $i$ 行包含两个整数 $l_i$ 和 $h_i$（$1 \leq l_i \leq h_i \leq 1\,000\,000$），表示客户要求书籍高度不小于 $l_i$ 且不大于 $h_i$。

所有测试数据中书籍总数不超过 $600\,000$，客户总数不超过 $1\,500\,000$。

输出格式

对于每位客户，输出满足其要求的非空连续书籍片段的数量。

2
10 3
9 9 3 2 1 9 6 9 1 7
1 13
6 6
2 9
5 1
66575 45720 67904 18764 35162
20000 80000

55
1
17
7