样例下载

题目描述

跳马游戏是一个改编的“跳格子”游戏。

$N$ 个格子排成一排，编号为 $1$ ~ $N$。其中 $N$ 是奇数。格子有黑、白两种颜色，编号为 $i$ 的格子颜色为 $C_i$（$C_i=0$ 表示格子是白格子，$C_i=1$ 表示格子是黑格子）。

初始时，你放了一匹马在 1 号格子里。你的目标是让它跳到 N 号格子里。

跳跃规则是：如果两匹马 A 与 B 处于相邻的两个格子里，若 B 的另一侧格子是空的，则 A 可以跳过 B 到另一侧的格子里并且吃掉 B 即把 B 从格子里拿走。当然，若 A 的另一侧格子是空的，B 也可以跳过 A 并且把 A 吃掉。如果另一侧的格子不是空的，则马是不可以跳跃的。

为此，你需要再放一些马帮助它们跳跃。

在游戏开始之前，你可以选任意个空格子放马，每个空格子里只能放一匹马。

一旦游戏开始之后，你只能选黑色空格子放马。

注意：这里所谓的游戏开始，是由你任意决定的。

你希望游戏开始之前，你放的马越少越好。

问：

（1）游戏开始之前，你至少需要放几匹马？

（2）在满足第（1）问的前提下，游戏开始之后，你至少需要再放几匹马？

注意：你只能往空格子里放马，并且你开始放的那匹马（称为原始马）不能在游戏中被吃掉。

输入格式

第一行：包含一个整数 $N$，数据保证 $N$ 是奇数。

第二行：包含 $N$ 个整数 $C_i$。

输出格式

共两行：

• 第一行：包含一个整数，表示游戏开始前至少放的马的数量

• 第二行：包含一个整数，表示满足第一行答案的前提下，游戏开始后至少放的马的数量。

样例1输入

5
0 1 0 0 0

样例1输出

1
1

样例1解释

游戏开始前：

在 4 号格子放一匹马。

然后你宣布游戏开始。

游戏开始后：

在 2 号格子放一匹马

然后原始马便可以依次跳过 2、4 到达目标。

样例2输入

5
0 0 0 1 1

样例2输出

0
4

样例2解释

游戏开始前，不需要放马。

游戏开始后：

在 4、5 号格子放两匹马，然后 5 吃掉 4 跳到 3 号格子。

在 4 号格子放一匹马，然后 4 吃掉 3 跳到 2 号格子。

则原始马从 1 号跳到 3 号格子，吃掉 2 号格子的马。

在 4 号格子放一匹马，然后原始马从 3 号格子跳到 5 号格子，到达目标。

数据范围

30% 的数据：$N < 20$。

100% 的数据：$1 ≤ N < 1000$ 数据保证答案均小于 $2^{63}$。