P12808 [AMPPZ 2019] Bookstore

**Time limit: 7s, memory limit: 512MB.**

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\} $. ```cpp 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.

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.

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