Henry loves plastic palindromes. However, he has run out of plastic.
So he turns to the next best thing, Paper Palindromes!
Inititally, Henry has a strip of paper with $N$ integers that can be represented as an array $a = [a_1, a_2, \dots, a_n] $.
Henry would like to perform some of the following operations
until the array becomes a single integer:
Let $M$ be the current size of the array.
- Henry changes the value of $a_i$ for any $1 \le i \le M$.
-
If the array is a palindrome, he may fold the array.
Formally, $a_M$ overlaps $a_1$, $a_{M-1}$ overlaps $a_2$, $\dots$ and the array $a$ becomes $[a_1, a_2, \dots, a_{\lceil{M/2}\rceil}]$.
Henry loves Paper Palindromes so much that he asks you to help him find the minimum number of operation $1$s such that $M=1$.
Input
The first line of the input contains one integer, $N$ — the initial size of the array $a$.
The second line of the input contains $N$ integers, $a_1,a_2,\dots,a_n $ $ (1 \le a_i \le 10^9)$ —
the integers on the paper initially.
Output
Output a single number, the minimum number of operation $1$s such that $M=1$.
Constraints
For all subtasks, $1\le N \le 10^5$, $1\le a_i\le 10^9$
Subtask 1 (5%): $a_i$ is distinct
Subtask 2 (20%): $1\le N\le 8$
Subtask 3 (30%): $1\le N\le 2000$
Subtask 4 (45%): No additional constraints
Sample Test Cases
| Input | Output | |
|---|---|---|
| 4 1 2 3 4 |
3 | |
| Change $[a_2, a_3, a_4]$ to 1 with 3 operation 1s. $[1,2,3,4]$ → $[1,1,1,1]$ → $[1,1]$ → $[1]$ |
||
| 5 1 2 1 2 1 |
1 | |
| Henry may fold the array twice, then change $a_2$ to 1 with an operation 1. $[1,2,1,2,1]$ → $[1,2,1]$ → $[1,2]$ → $[1]$ |
||
| 8 1 2 3 2 1 2 3 2 |
4 | |
Scoring: Per Subtask
Authored by s19x17
Appeared in 2023 Mini Contest 3 (Pre-TFT)