Квадратные числа
В волшебном мире квадратных корней () число считается «привлекательным», если оно является квадратным числом (1, 4, 9, 16, 25, 36, 49 и т.д.). Квадратные числа — это квадраты целых чисел (например, 4 — это квадрат 2, а 25 — это квадрат 5).
Пусть у нас есть
n чисел и q запросов по форме «Сколько привлекательных чисел содержится в диапазоне [li; ri]?». Требуется написать программу, которая сможет быстро отвечать на такие вопросы.Входные данные
Первая строка входа содержит два целых числа —
n, количество элементов в массиве (1 ≤ n ≤ ), и q, количество запросов (1 ≤ q ≤ ).Следующая строка содержит
n целых чисел, разделенных пробелами, которые представляют элементы массива ().Каждая из следующих
q строк содержит по два целых числа l_i и r_i (), задающих диапазон запроса (включительно).Выходные данные
Необходимо вывести
q строк, в каждой из которых будет указано количество привлекательных чисел на отрезке .Примеры
Входные данные | Выходные данные |
6 4
9 5 2 4 16 3
0 5
0 1
1 2
2 5 | 3
1
0
2 |
Constraints
Time limit: 6 seconds
Memory limit: 512 MB
Output limit: 5 MB