← 返回题目列表

Codeforces · 1286/A

A. 花环

中文机器翻译题面 查看原题

Vadim 喜欢装饰圣诞树,所以他得到了一个漂亮的花环作为礼物。它由单排的 $$$n$$$ 个灯泡组成。每个灯泡都有一个从 $$$1$$$ 到 $$$n$$$ 的数字(按任意顺序),因此所有数字都是不同的。当瓦迪姆解决问题时,他的家卡普从花环上取下了一些灯泡。现在瓦迪姆想把它们重新穿上。

Vadim 想要将所有灯泡放回花环上。 Vadim 将花环的复杂度定义为具有不同奇偶性的数字的相邻灯泡对的数量(除以 $$$2$$$ 的余数)。例如,1 4 2 3 5 的复杂度为 $$$2$$$,1 3 5 7 6 4 2 的复杂度为 $$$1$$$。

没有人喜欢复杂性,因此 Vadim 希望最大限度地减少此类对的数量。找到将所有灯泡放回花环上的方法,使复杂性尽可能小。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 100$$$) — 花环上灯泡的数量。

第二行包含 $$$n$$$ 整数 $$$p_1,\ p_2,\ \ldots,\ p_n$$$ ($$$0 \le p_i \le n$$$) — 第 $$$i$$$ 个灯泡上的数字,如果已移除,则为 $$$0$$$。

输出

输出一个数字——花环的最小复杂度。

示例

输入 #1

5
0 5 0 2 3

输出 #1

2

输入 #2

7
1 0 0 5 0 0 2

输出 #2

1

注意

在第一个示例中,应将灯泡放置为 1 5 4 2 3。在这种情况下,复杂度将等于 2,因为只有 $$$(5, 4)$$$ 和 $$$(2, 3)$$$ 是具有不同奇偶性的相邻灯泡对。

在第二种情况下,正确答案之一是 1 7 3 5 6 4 2。