CF1286A Garland

Vadim 喜欢装饰圣诞树，所以他收到了一串漂亮的彩灯作为礼物。这串彩灯由 $n$ 个灯泡组成，排成一行。每个灯泡上标有 $1$ 到 $n$ 之间的一个数字（顺序任意），且所有数字互不相同。当 Vadim 在解题时，他家的 Carp 拆掉了彩灯上的一些灯泡。现在 Vadim 想把它们重新装回去。 Vadim 想要把所有灯泡都重新装回彩灯上。他定义彩灯的复杂度为相邻灯泡编号奇偶性不同的相邻对的数量。例如，$1\ 4\ 2\ 3\ 5$ 的复杂度为 $2$，因为只有 $(5, 4)$ 和 $(2, 3)$ 这两对相邻灯泡的编号奇偶性不同。又如，$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\ 4\ 2\ 3$ 的顺序放置。此时复杂度为 $2$，因为只有 $(5, 4)$ 和 $(2, 3)$ 这两对相邻灯泡的编号奇偶性不同。 在第二个样例中，其中一种正确的答案是 $1\ 7\ 3\ 5\ 6\ 4\ 2$。 由 ChatGPT 4.1 翻译