Задача B. Перестановки ≡

Автор:Жюри всероссийских зимних сборов школьников 2007-2008   Ограничение времени:2 сек
Входной файл:permutation.in   Ограничение памяти:64 Мб
Выходной файл:permutation.out  
Максимальный балл:100  

Условие

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

Формат входного файла

В первой строке лежит два натуральных числа — N — количество чисел, которые выписал Вася и M количество вопросов, которые Вася хочет задать программе. Во второй строке дано N чисел — последовательность чисел, выписанных Васей. Далее в M строках находятся описания вопросов. Каждая строка содержит четыре целых числа x y k l.

Формат выходного файла

Выведите M строк, каждая должна содержать единственное число — ответ на Васин вопрос.

Ограничения

1 ≤ N ≤ 105

1 ≤ M ≤ 105

1 ≤ x ≤ y ≤ N

1 ≤ k ≤ l ≤ N

Примеры тестов

№ Входной файл (permutation.in) Выходной файл (permutation.out)
1 
4 2
1 2 3 4
1 2 2 3
1 3 1 3
 
1
3
0.060s 0.008s 13