Permutations
Vasya has written all the numbers from 1 to N 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 x and y, fall within the range from k to l?
Your task is to replicate this functionality.
Input
The first line contains two natural numbers: 1 ≤ N ≤ 100000, representing the total numbers Vasya wrote, and 1 ≤ M ≤ 100000, the number of queries Vasya wants to make. The second line lists N integers, representing the sequence Vasya wrote. The following M lines each describe a query with four integers: 1 ≤ x ≤ y ≤ N and 1 ≤ k ≤ l ≤ N.
Output
For each of the M queries, output a single line containing the answer to Vasya's question.