У вас есть массив \(a\) длины \(n\). Для каждого положительного числа \(x\) в течение \(x\)-й секунды вы собираетесь выполнить следующую операцию:
- Выберите несколько различных индексов \(i_{1}, i_{2}, \ldots, i_{k}\), которые находятся в диапазоне от \(1\) до \(n\) включительно, и добавьте \(2^{x-1}\) к каждой соответствующей позиции в \(a\). Формально \(a_{i_{j}} := a_{i_{j}} + 2^{x-1}\) для \(j = 1, 2, \ldots, k\). Обратите внимание, что вы можете также не выбрать ни одного индекса.
Вы должны сделать \(a\) неубывающим как можно быстрее. Найдите наименьшее число \(T\) такое, что вы можете сделать массив неубывающим не позднее, чем через \(T\) секунд.
Массив \(a\) называется неубывающим, если и только если \(a_{1} \le a_{2} \le \ldots \le a_{n}\).
Вы должны ответить на \(t\) независимых тестовых случаев.
Выходные данные
Для каждого тестового примера выведите минимальное количество секунд, за которое вы можете сделать \(a\) неубывающим.
Примечание
В первом тестовом случае, если вы выберете индексы \(3, 4\) на \(1\)-й секунде и \(4\) на \(2\)-й секунде, то \(a\) станет равным \([1, 7, 7, 8]\). Есть и другие способы сделать \(a\) неубывающим за \(2\) секунды, но вы не сделать его неубывающим быстрее.
Во втором тестовом случае \(a\) уже неубывающий, поэтому ответ равен \(0\).
В третьем тестовом случае, если вы ничего не сделаете в первые \(2\) секунды и в течение \(3\)-й секунды выберете индекс \(2\), \(a\) станет равным \([0, 0]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
4
1 7 6 5
5
1 2 3 4 5
2
0 -4
|
2
0
3
|