Изначально есть массив нулей \(a_1, a_2, \ldots, a_n\) длины \(n\).
Вы можете выполнять операции двух типов:
- Выбрать индекс \(i\) такой, что \(1 \le i \le n\) и \(a_i = 0\), после чего записать в \(a_i\) значение \(1\);
- Выбрать индексы \(l\) и \(r\) такие, что \(1 \le l \le r \le n\), \(a_l = 1\), \(a_r = 1\) и \(a_l + \ldots + a_r \ge \lceil\frac{r - l + 1}{2}\rceil\), после чего записать значение \(1\) в \(a_i\) для всех \(l \le i \le r\).
За какое минимальное количество операций первого типа вы можете получить массив, все элементы которого равны единице?
Выходные данные
Для каждого набора входных данных выведите единственное число — минимальное количество операций первого типа.
Примечание
В первом наборе можно выполнить операцию \(1\)-го типа с \(i = 1\).
Во втором наборе можно выполнить следующую последовательность операций:
- Операция \(1\)-го типа, \(i = 1\). После выполнения этой операции массив будет выглядеть так: \([1, 0]\).
- Операция \(1\)-го типа, \(i = 2\). После выполнения этой операции массив будет выглядеть так: \([1, 1]\).
Последовательность операций во втором тесте 
В третьем наборе можно выполнить следующую последовательность операций:
- Операция \(1\)-го типа, \(i = 1\). После выполнения этой операции массив будет выглядеть так: \([1, 0, 0, 0]\).
- Операция \(1\)-го типа, \(i = 4\). После выполнения этой операции массив будет выглядеть так: \([1, 0, 0, 1]\).
- Операция \(2\)-го типа, \(l = 1\), \(r = 4\). На данном отрезке \(a_l + \ldots + a_r = a_1 + a_2 + a_3 + a_4 = 2\), что не меньше, чем \(\lceil\frac{r - l + 1}{2}\rceil = 2\). После выполнения этой операции массив будет выглядеть так: \([1, 1, 1, 1]\).
Последовательность операций в третьем тесте 
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1
2
4
20
|
1
2
2
4
|