[Ahoi2009]checker

在一个 $1$ 行 $N$ 列（$N$ 是奇数）的棋盘上，有 $K$ 个格子是红色的。这种情况下，你有一个跳棋在最左端的格子上，你的目标是将它移动到最右边的格子。

在开始移动之前，你可以在棋盘的任意空位上放棋子。在游戏开始后，你只可以随时在一个红色格子上放棋子。

棋子的移动规则是：每次只可以选择一个棋子，跳过与之相邻的棋子走到后面的空格上，被它跳过的棋子被吃掉，即从棋盘上移走；如相邻棋子的另一侧有棋子，则不能跳。

请回答以下两个问题：

1. 移动开始前至少要放多少棋子才能完成任务；
2. 如果要使开始前放的棋子数尽量少，那么在移动过程中最少需要放多少个棋子才能完成任务。

关于规则的补充说明：

• 只能往空位上放棋子，不管是移动开始前还是移动过程中；
• 移动前棋盘最左端的那个原始棋子绝对不能被吃掉。

输入格式

第一行一个正奇数 $N$。

第二行有 $N$ 个整数，如果第 $i$ 个整数非零，说明第 $i$ 个格子是红色的，否则为白色的。数字间用空格分开。

输出格式

两个数字，分别代表第一问和第二问的结果。

样例输入

5
0 0 0 1 0

样例输出

1
1

样例解释

在游戏开始前，可以在第二个格子上放上一个棋子，游戏开始后可用最左边的棋子吃掉它，从而移动到第三格。然后由于第四格是个红色的格子，在游戏中可以在那放一个棋子，然后用已经移动到第三格的棋子把它吃掉，从而达到终点。

数据范围

• 对于 $100\%$ 的数据，$N\le 1000$，输出中的数字不超过 $10^{15}$；
• 对于 $30\%$ 的数据，$N\le 20$。

来源与许可

本题为 AHOI 2009 试题「checker」，题面与测试数据整理自 BZOJ 1802。

样例 1

输入

5
0 0 0 1 0

输出

1
1