Problems
Перестановки
Перестановки
Вася выписал на доске в каком-то порядке все числа от \textbf{1} до \textbf{N}, каждое число ровно по одному разу. Количество чисел оказалось довольно большим, поэтому Вася не может окинуть взглядом все числа. Однако ему надо всё-таки представлять эту последовательность, поэтому он написал программу, которая отвечает на вопрос - сколько среди чисел, стоящих на позициях с \textbf{x} по \textbf{y}, по величине лежат в интервале от \textbf{k} до \textbf{l}.
Сделайте то же самое.
\InputFile
В первой строке лежит два натуральных числа - \textbf{1} ≤ \textbf{N} ≤ \textbf{100000} - количество чисел, которые выписал Вася, и \textbf{1} ≤ \textbf{M}≤ \textbf{100000} - количество вопросов, которые Вася хочет задать программе. Во второй строке дано \textbf{N} чисел - последовательность целых чисел, выписанных Васей. Далее в \textbf{M} строках находятся описания вопросов. Каждая строка содержит четыре целых числа \textbf{1} ≤ \textbf{x} ≤ \textbf{y} ≤ \textbf{N} и \textbf{1} ≤ \textbf{k} ≤ \textbf{l} ≤ \textbf{N}.
\OutputFile
Выведите \textbf{M} строк, каждая должна содержать единственное число - ответ на Васин вопрос.
Input example #1
4 2 1 2 3 4 1 2 2 3 1 3 1 3
Output example #1
1 3