2.4 Making a Palindromic Array
(RankList for this Question)
JJ has an array A of length N initially. He has a special operation available, which allows him to modify the array as follows:
1. Choose an index i (1 ≤ i ≤ |A|) such that Ai > 1.
2. Select two integers X and Y (X + Y = Ai) with X, Y ≥ 1.
3. Replace Ai with X and Y.
Note that after each operation, the length of the array increases by 1. JJ's goal is to make the array A palindromic, i.e., an array that reads the same forwards and backwards. Find the minimum number of operations required to achieve this goal.
It is guaranteed that A can be converted into a palindromic array using the given operation.
Constraints
1≤T≤105
1≤N≤10^5
1≤Ai≤10^5
Sum of N over all test cases does not exceed 2⋅10^5
Input Format
-The first line contains a single integer T — the number of test cases. Then the test cases follow.
-The first line of each test case contains an integer N — the size of the array A.
-The second line of each test case contains N space-separated integers A1,A2,…,AN denoting the array A.
Output Format
For each test case, output the minimum number of operations to make A palindromic.
Example 1
Input:
3
4
3 7 6 4
5
1 4 5 4 1
5
1 2 3 4 5
Output:
2
0
4
Explanation:
Test Case 1: We can perform the following operations:
[3,7,6,4]
lets i=2,X=1,Y=6,
so transforms to [3,1,6,6,4]
[3,1,6,6,4]
lets i=5,X=1,Y=3
[3,1,6,6,1,3]
so ans is 2.
Test Case 2: A is already palindromic
so ans is 0
Log In to solve the Question