E. Split
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\).
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\).
For each test case, print a single line containing one integer — the minimum possible value of \(|b|\).