ikrpprpp нашел массив \(a\), состоящий из целых чисел. Ему нравится справедливость, поэтому он хочет сделать \(a\) честным — то есть сделать его неубывающим. Для этого он может выполнить акт справедливости на индексе \(1 \le i \le n\) массива, который заменит \(a_i\) на \(a_i ^ 2\) (элемент на позиции \(i\) на его квадрат). Например, если \(a = [2,4,3,3,5,3]\) и ikrpprpp решает выполнить акт справедливости на \(i = 4\), то \(a\) становится \([2,4,3,9,5,3]\).
Каково минимальное количество актов справедливости, необходимых для того, чтобы сделать массив неубывающим?
Выходные данные
Для каждого набора входных данных выведите целое число — минимальное количество актов справедливости, необходимых для того, чтобы сделать массив \(a\) неубывающим. Если это невозможно, выведите \(-1\).
Примечание
В первом наборе входных данных нет необходимости выполнять акты справедливости. Массив сам по себе честен!
В третьем наборе входных данных можно доказать, что массив не может стать неубывающим.
В пятом наборе входных данных ikrpprppp может выполнить акт справедливости на индексе 3, затем акт справедливости на индексе 2 и, наконец, еще один акт справедливости на индексе 3. После этого \(a\) станет \([4, 9, 16]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
3
1 2 3
2
3 2
3
3 1 5
4
1 1 2 3
3
4 3 2
9
16 2 4 2 256 2 4 2 8
11
10010 10009 10008 10007 10006 10005 10004 10003 10002 10001 10000
|
0
1
-1
0
3
15
55
|