eolymp
bolt
Try our new interface for solving problems
Məsələlər

Перестановки

Перестановки

Zaman məhdudiyyəti 2 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB

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

Сделайте то же самое.

Giriş verilənləri

В первой строке лежит два натуральных числа - 1N100000 - количество чисел, которые выписал Вася, и 1M100000 - количество вопросов, которые Вася хочет задать программе. Во второй строке дано N чисел - последовательность целых чисел, выписанных Васей. Далее в M строках находятся описания вопросов. Каждая строка содержит четыре целых числа 1xyN и 1klN.

Çıxış verilənləri

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

Nümunə

Giriş verilənləri #1
4 2
1 2 3 4
1 2 2 3
1 3 1 3
Çıxış verilənləri #1
1
3