Підрахунок стогів сіна

Вхідні дані

Перший рядок містить $n (1 \leq n \leq 1 0^{5})$ n~(1 \le n \le 10^5) і $q (1 \leq q \leq 1 0^{5})$ q~(1 \le q \le 10^5). Наступний рядок містить $n$ різних цілих чисел, кожне в діапазоні $0 ... 1 0^{9}$ 0~...~10^9, що вказують на розташування стогів сіна.

Кожен з наступних $q$ рядків містить два цілі числа $a$ і $b (0 \leq a \leq b \leq 1 0^{9})$ b~(0 \le a \le b \le 10^9), які визначають запит на кількість стогів сіна між $a$ і $b$ , включно.

Вихідні дані

Виведіть $q$ рядків. Для кожного запиту виведіть кількість стогів сіна у відповідному інтервалі.

Приклади

Приклад 1

Loading