Background

Special for beginners, ^_^

Description

给定一个长度为 $n$ 的整数数列 $a_1,a_2,\cdots,a_n$。你可以执行若干次操作，每次操作选定一个整数 $x$（$1\le x\le n$） 和一个整数 $k$，然后令 $a_x\gets k$，使得所有操作结束后：

1. 整个数列是回文的，即 $\forall i\in\{1,2,\cdots,n\}$，$a_i=a_{n-i+1}$；
2. 数列的前一半是严格递增的，即 $\forall i\in\{1,2,\cdots, \lceil n/2\rceil-1\}$，$a_i<a_{i+1}$。

请求出最少操作次数。

Format

Input

第一行一个正整数 $n$，表示数列长度；

第二行 $n$ 个正整数表示数列。

本题读入规模较大，请使用效率较高的读入方式。

Output

一个整数表示答案。

Samples

5
1 2 3 2 1

0

5
1 3 3 2 1

1

Limitation

对于全部数据，$1\le n\le5\cdot 10^5,\;-10^9\le a_i\le 10^9$。

特殊性质：答案小于等于 $2$。