Ирис только что научилась умножению на уроках математики. Однако, поскольку её мозг не в состоянии выдерживать слишком сложные вычисления, она не может перемножать два целых числа, произведение которых больше \(k\). В противном случае её мозг может взорваться!
Её учитель каждый день даёт ей сложную задачу в качестве домашнего задания на летних каникулах. Теперь ей дан массив \(a\), состоящий из \(n\) элементов, и ей нужно вычислить произведение каждой пары соседних элементов (то есть, \(a_1 \cdot a_2\), \(a_2 \cdot a_3\) и так далее). Ирис хочет, чтобы её мозг не перегружался, и для этого она хотела бы изменить массив \(a\) так, чтобы выполнялось условие \(a_i \cdot a_{i + 1} \leq k\) для всех \(1 \leq i < n\). Она может выполнять два типа операций:
- Она может переставить элементы массива \(a\) произвольным образом.
- Она может выбрать произвольный элемент массива \(a\) и изменить его значение на произвольное целое число от \(1\) до \(k\).
Ирис хочет минимизировать количество операций типа \(2\), которые она использует.
Однако это совершенно не конец летних каникул! Летние каникулы длятся \(q\) дней, и в \(i\)-й день Ирис просят решить математическое задание для подмассива \(b_{l_i}, b_{l_i + 1}, \ldots, b_{r_i}\). Помогите Ирис и скажите ей минимальное количество операций типа \(2\), которые ей нужно выполнить для каждого дня. Обратите внимание, что операции независимы для каждого дня, то есть массив \(b\) не изменяется.
Выходные данные
Для каждого набора входных данных выведите одну строку, содержащую \(q\) целых числа — минимальное количество операций типа \(2\), необходимых для каждого дня.
Примечание
В первом наборе входных данных, так как Ирис всегда может перемножить \(1\) и \(1\), операции не требуются, поэтому ответ равен \(0\).
Во втором наборе входных данных, домашнее задание первого дня — \([1, 10, 9]\). Ирис может переставить его элементы, чтобы получить \([9, 1, 10]\), поэтому операции типа \(2\) не требуются. Домашнее задание второго дня — \([10, 9]\), и она может изменить один элемент, чтобы получить массив \([1, 9]\), поэтому требуется одна операция типа \(2\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
3 1 1
1 1 1
1 3
3 2 10
1 10 9
1 3
2 3
5 4 2
2 2 2 2 2
1 2
2 4
2 5
1 5
6 5 10
3 2 5 10 10 1
1 4
3 6
1 6
2 5
5 6
10 10 10
10 9 8 7 6 5 4 3 2 1
1 10
1 9
1 8
1 7
2 10
3 10
4 10
5 10
3 9
6 8
|
0
0 1
1 1 2 2
1 1 1 1 0
3 3 4 3 2 2 1 1 2 1
|