Permutations#3616
Vasya has written all the numbers from to on a board in a unique order, with each number appearing exactly once. Since the list is quite extensive, Vasya can't easily see all the numbers at once. To help visualize the sequence, he developed a program that answers the question: how many numbers, located between positions and , fall within the range from to ?
Your task is to replicate this functionality.
The first line contains two natural numbers: 1 \leq N \leq 100000, representing the total numbers Vasya wrote, and 1 \leq M \leq 100000, the number of queries Vasya wants to make. The second line lists integers, representing the sequence Vasya wrote. The following lines each describe a query with four integers: 1 \leq x \leq y \leq N and 1 \leq k \leq l \leq N.
For each of the queries, output a single line containing the answer to Vasya's question.
Primer 1