Minimum Subarray Reversals to Make Palindrome

You are given a sequence of integers. Your task is to determine the minimum number of subarray reversals required to transform the given sequence into a palindrome.

A palindrome is a sequence that reads the same forwards and backwards. In one operation, you may choose any contiguous subarray and reverse it. The goal is to achieve a palindrome using the minimum number of such operations.

The problem can be solved using dynamic programming. One approach is to use a DP table where dp[i][j] represents the minimum number of operations needed to turn the subarray from index i to j into a palindrome. The transition is defined using the formula:

\(dp[i][j]=\begin{cases} dp[i+1][j-1] & \text{if } a_i = a_j,\\ \min(dp[i][j-1], dp[i+1][j]) + 1 & \text{otherwise.} \end{cases}\)

Note that for sequences of length 0 or 1, the answer is 0.

inputFormat

The first line contains a single integer n (where n ≥ 0), representing the number of elements in the sequence.

If n is greater than 0, the second line contains n space-separated integers representing the sequence.

If n is 0, there will be no second line.

outputFormat

Output a single integer representing the minimum number of subarray reversals required to make the sequence a palindrome.

## sample

1
1

0