Это усложненная версия этой задачи. Разница между легкой и сложной версиями заключается в ограничениях на \(a_i\) и на \(n\). Вы можете делать взломы только в том случае, если обе версии задачи решены.
Бурёнка — наследная принцесса Бурятии, и скоро она станет \(n\)-й по счёту королевой страны. В Бурятии есть древняя традиция — правитель перед своей коронацией должен показать жителям свою силу. Чтобы определить силу \(n\)-го правителя, жители страны дают ему массив \(a\) из ровно \(n\) чисел, после чего он должен превратить все элементы массива в нули за наименьшее время. Правитель может любое число раз выполнить следующую операцию из двух шагов:
- выбрать два индекса \(l\) и \(r\) такие, что \(1 \le l \le r \le n\) и целое неотрицательное число \(x\), затем
- для всех \(l \leq i \leq r\) присвоить \(a_i := a_i \oplus x\), где \(\oplus\) обозначает операцию побитового исключающего ИЛИ. На эту операцию он потратит \(\left\lceil \frac{r-l+1}{2} \right\rceil\) секунд, где \(\lceil y \rceil\) обозначает округление числа \(y\) вверх до ближайшего целого.
Помогите Буренке посчитать, сколько времени ей понадобится.
Выходные данные
Для каждого набора входных данных выведите единственное число — минимальное время, которое понадобится Буренке.
Примечание
В первом наборе входных данных Бурёнка может выбрать индексы \(l = 1\), \(r = 4\) и \(x=5\). так он заполнит массив нулями за \(2\) секунды.
Во втором наборе входных данных Бурёнка сначала выбирает индексы \(l = 1\), \(r = 2\) и \(x = 1\), после чего \(a = [0, 2, 2]\), а затем индексы \(l = 2\), \(r = 3\) и \(x=2\), что заполняет массив нулями. Суммарно Бурёнка потратит \(2\) секунды.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
4
5 5 5 5
3
1 3 2
2
0 0
3
2 5 7
6
1 2 3 3 2 1
10
27 27 34 32 2 31 23 56 52 4
5
1822 1799 57 23 55
|
2
2
0
2
4
7
4
|