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