(RankList for this Question)
2.4 Making a Palindromic Array
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.
Sum of N over all test cases does not exceed 2⋅10^5
-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.
For each test case, output the minimum number of operations to make A palindromic.
3 7 6 4
1 4 5 4 1
1 2 3 4 5
Test Case 1: We can perform the following operations:
so transforms to [3,1,6,6,4]
so ans is 2.
Test Case 2: A is already palindromic
so ans is 0
Log In to solve the Question