题目描述

小王正在玩一款新的即时战略游戏。他有一个军团，排成一排$n$个士兵，每个士兵都由系统随机分配了一个外观，用整数表示，这$n$个士兵的外观分别为$a_1,a_2....,a_n$。小王想要拥有一支整齐外观的军团，于是打开了他的游戏编辑器。游戏编辑器允许小王选择一个长度为不大于$n$的任意偶数(例如$2m$)的区间$[L,L+2m-1]$($1 \leq L \leq n=2m+1$，注意小王选择的区间不能超过士兵范围)使得对于其中左半区间内十兵的外观设置为右半区间士兵的外观。形式化地，游戏编辑器会做这样的操作: 对于给定$2m$和$L$，设置$ai=ai+m (L \leq i \leq L+m-1)$。小干想知道他至少做多少次这样的拷贝操作，能让他军团中所有士兵拥有相同的外观。

输入描述

第一行$1$个整数为$n$，表示士兵数量。

第二行$n$个整数$a_1 a_2 ....a_n$,分别表示这n个士兵的外观

$1 \leq n \leq 50000，1 \leq a_i \leq n$

输出描述

输出一行一个数表示最少拷贝操作数量，使得所有士兵拥有相同外观。

样例

输入

4
1 2 2 2

输出

1

提示

输入样例$2$

$4$

$1$ $2$ $3$ $4$

输出样例$2$

$2$

样例解释

样例$1$中，选择区间$[1，2]$，将第二个士兵的外观拷贝给第一个士兵即可让所有士兵拥有相同的外观。

样例$2$中，可以将区间$[3，4]$进行拷贝，变为$1$ $2$ $4$ $4$，之后对区间$[1， 4]$拷贝即可让所有士兵拥有相同的外观，共两次操作。