Перестановки
Вася выписал на доске в каком-то порядке все числа от 1 до N, каждое число ровно по одному разу. Количество чисел оказалось довольно большим, поэтому Вася не может окинуть взглядом все числа. Однако ему надо всё-таки представлять эту последовательность, поэтому он написал программу, которая отвечает на вопрос - сколько среди чисел, стоящих на позициях с x по y, по величине лежат в интервале от k до l.
Сделайте то же самое.
Входные данные
В первой строке лежит два натуральных числа - 1 ≤ N ≤ 100000 - количество чисел, которые выписал Вася, и 1 ≤ M≤ 100000 - количество вопросов, которые Вася хочет задать программе. Во второй строке дано N чисел - последовательность целых чисел, выписанных Васей. Далее в M строках находятся описания вопросов. Каждая строка содержит четыре целых числа 1 ≤ x ≤ y ≤ N и 1 ≤ k ≤ l ≤ N.
Выходные данные
Выведите M строк, каждая должна содержать единственное число - ответ на Васин вопрос.