Description

You own a very peculiar bookstore, which sells old books, but you store all of them on a single shelf, in random order, and you do not care about the books’ content. Nor do your clients – they tend to come into the store and simply ask for “all the books on that shelf, starting from this one and ending here”. To be precise, every client buys some connected (and non-empty) fragment of books from the shelf.

Sometimes, though, you get more picky clients, who expect more from a book – actually, they expect it to have the right size. A picky client wants a fragment of shelf in which all the books have their height not smaller than $l$ and not greater than $h$.

Given a sequence of integers – the heights of all the books on the shelf – determine the number of possible connected fragments which satisfy these requirements.

Also, we mentioned that the books are in random order. Formally, the input sequence was generated with the following program, for some values of $N \in \{1, 2, \ldots, 100000\}$ and $M = 10^q$ with $q \in \{1, 2, \ldots, 6\}$.

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

You do not actually need to know how the RAND48 library works. It is enough to assume that the function lrand48 returns 31-bit non-negative integers picked uniformly at random.

Input Format

The first line of input contains the number of test cases $z$ ($1 \leq z \leq 5$). The test cases follow, each one in the following format:

• The first line of a test case contains the number of books $n$ and the number of picky clients $k$ ($1 \leq n \leq 200000$, $1 \leq k \leq 500000$).
• The second line contains a sequence of $n$ positive integers not exceeding 1 000 000 – the heights of all the books, from the first (leftmost) to the last (rightmost) one.
• The final $k$ lines describe the clients’ requirements. The $i$-th of these lines contains two integers $l_i, h_i$ ($1 \leq l_i \leq h_i \leq 1000000$), describing a client that wants books to be not smaller than $l_i$ and not greater than $h_i$.

The total number of books in all test cases does not exceed 600 000, and the total number of clients in all test cases does not exceed 1 500 000.

Output Format

For every client, output the number of non-empty connected fragments of the book sequence which satisfy the client’s requirements.

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