Split
Contest: Codeforces Round 673 (Div. 1)
Difficulty rating: 3200
Tags: binary search, data structures, dp, greedy

One day, BThero decided to play around with arrays and came up with the following problem:

You are given an array $$$a$$$, which consists of $$$n$$$ positive integers. The array is numerated $$$1$$$ through $$$n$$$. You execute the following procedure exactly once:

- You create a new array $$$b$$$ which consists of $$$2n$$$ positive integers, where for each $$$1 \le i \le n$$$ the condition $$$b_{2i-1}+b_{2i} = a_i$$$ holds. For example, for the array $$$a = [6, 8, 2]$$$ you can create $$$b = [2, 4, 4, 4, 1, 1]$$$.
- You merge consecutive equal numbers in $$$b$$$. For example, $$$b = [2, 4, 4, 4, 1, 1]$$$ becomes $$$b = [2, 4, 1]$$$.

Find and print the minimum possible value of $$$|b|$$$ (size of $$$b$$$) which can be achieved at the end of the procedure. It can be shown that under the given constraints there is at least one way to construct $$$b$$$.

Input format:
The first line of the input file contains a single integer $$$T$$$ ($$$1 \le T \le 5 \cdot 10^5$$$) denoting the number of test cases. The description of $$$T$$$ test cases follows.

The first line of each test contains a single integer $$$n$$$ ($$$1 \le n \le 5 \cdot 10^5$$$).

The second line contains $$$n$$$ space-separated integers $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$2 \le a_i \le 10^9$$$).

It is guaranteed that $$$\sum{n}$$$ over all test cases does not exceed $$$5 \cdot 10^5$$$.

Output format:
For each test case, print a single line containing one integer — the minimum possible value of $$$|b|$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
3
3
6 8 2
1
4
3
5 6 6

Example output:
3
1
2

Editorial:
Note that minimizing $$$|b|$$$ is the same as maximizing the number of consecutive equal pairs. We will focus on the second version.
Let's forget about constraints and consider the most naive solution with dynamic programming. $$$DP[i][j]$$$ will store the answer if we have already considered ($$$a_1$$$, ..., $$$a_i$$$) and our last element $$$b_{2i}$$$ is equal to $$$j$$$.
Let's get rid of our dimension $$$i$$$ and keep our $$$DP$$$ table by layers. Suppose that our current $$$i$$$-th layer is called $$$curDP$$$, next layer is called $$$nxtDP$$$, and $$$a_{i+1}$$$ is called $$$X$$$.
After carefully analyzing our transitions, we have the following observations:
• for any $$$i$$$, $$$nxtDP[i] \ge max(curDP)$$$, since we always have a transition from our maximum.
• $$$max(nxtDP[i]) - min(nxtDP[i]) \le 2$$$, since we can add at most two pairs.
• The case $$$max(nxtDP[i]) - min(nxtDP[i]) = 2$$$ may occur only if $$$a_i$$$ is even. Moreover, $$$nxtDP[a_i/2]$$$ will be the only maximum element.
• For some suffix upto $$$i$$$ we always have a transition from $$$curDP[X-i] + 1$$$ to $$$nxtDP[i]$$$.
• If $$$X$$$ is even, instead of calculating $$$nxtDP[X/2]$$$ separately, we can calculate it as usual and increase its value by $$$1$$$ at the end.
Using everything said above, we could replace our naive $$$DP$$$ with the following:
1. A variable called $$$zero$$$ — the value of minimum of our current layer.
2. A set called $$$one$$$ — it keeps all indices $$$i$$$ such that $$$curDP[i] = zero + 1$$$.
3. A variable called $$$two$$$ — it is equal to $$$-1$$$ or $$$X/2$$$ depending on the parity of $$$X$$$ and the value of $$$curDP[X/2]$$$.
Basically, we want to be able to:
• Erase some elements from the prefix/suffix of our set $$$one$$$.
• Check if some number $$$x$$$ is in our set $$$one$$$.
• Add a segment of values $$$[l, r]$$$ into out set $$$one$$$.
• Rotate all elements in our set by a pivot $$$x$$$. That is, a number $$$y$$$ should turn into $$$x-y$$$.
We can efficiently process all queries by maintaining $$$one$$$ as a simple set of non-intersecting segments. The rotation operation can be done as follows:
1. Suppose we had an integer $$$X$$$ at the beginning.
2. We rotate everything by a pivot $$$A$$$. $$$X$$$ becomes $$$A-X$$$.
3. We rotate everything by a pivot $$$B$$$. $$$A-X$$$ becomes $$$B-A+X$$$.
4. Following the logic, $$$C-B+A-X$$$, $$$D-C+B-A+X$$$, ...
5. We can just maintain the sign of $$$X$$$ and a global pivot, which is the combination of all our rotation operations.
Time complexity: $$$O(n \log n)$$$
Space complexity: $$$O(n)$$$