Перестановки
Вася виписав на дошці у якомусь порядку усі числа від 1 до N, кожне число рівно по одному разу. Кількість чисел виявилась досить великою, тому Вася не може окинути поглядом усі числа. Проте йому потрібно усе-таки уявляти цю послідовність, тому він написав програму, яка відповідає на питання - скільки среди чисел, які стоять на позиціях з x по y, по величині лежать в інтервалі від k до l.
Зробіть те ж саме.
Вхідні дані
У першому рядку лежить два натуральних числа - 1 ≤ N ≤ 100000 - кількість чисел, які виписав Вася, і 1 ≤ M ≤ 100000 - кількість запитань, які Вася хоче задати програмі. У другому рядку задано N чисел - послідовність цілих чисел, виписаних Васею. Далі в M рядках знаходяться описи запитань. Кожен рядок містить чотири цілих числа 1 ≤ x ≤ y ≤ N и 1 ≤ k ≤ l ≤ N.
Вихідні дані
Виведіть M рядків, кожен повинен містити єдине число - відповідь Васине запитання.