You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

给你一个由 $n(n>2)$ 个点构成的环，标号为 $1$ 到 $n$，其中 $i$ 和 $i + 1$ 相连，$1$ 和 $n$ 相连。每个点上写了一个数 $a_i$，这个数只可能是 $0$ 或 $1$。

辰辰 认为，如果相邻两个点的数不一样，那么这个环就会不好看。但是如果环上同时存在 $0, 1$，那么必定存在相邻两个数不一样。所以 辰辰 想尽量减少相邻不一样的数的个数。

环的不美观值是 $[a_1 \neq a_n] + \sum_{i=1}^{n-1} [a_i\neq a_{i + 1}]$,即对于任意相连的两个点 $x, y$，如果 $a_x \neq a_y$ 则会贡献 $1$ 的不美观值。

每次操作可以交换相邻两个点 $x, y$ 对应的数 $a_x, a_y$，辰辰 想知道，如何用最少的步数，将环的不美观值降到最低。输出这个步数。

输入格式

第一行一个正整数 $n$，表示环的长度。

第二行 $n$ 个仅在 $\{0, 1\}$ 取值的整数，第 $i$ 个表示 $a_i$。

输出格式

一个非负整数，表示最小化不美观值的最小步数。

8
0 1 0 0 1 0 1 0

3

样例解释

第 $1$ 个 $1$ 向右交换两次, 第 $3$ 个 $1$ 向左交换一次, 最终序列为 0 0 0 1 1 1 0 0

数据范围与约定

对所有数据，有 $1 \leq n \leq 2 \times 10^5$。

对于 $10\%$ 的数据，$n \leq 20$。

对于 $30\%$ 的数据，$n \leq 300$。

对于 $60\%$ 的数据，$n \leq 5000$。

对于 $100\%$ 的数据，没有其他限制。

提示

中位数_百度百科 (baidu.com)