Pavel Petrovich 在“Rodina”文化宫的一家乒乓球俱乐部担任教练。

俱乐部里有一对兄弟：Artyom 和 Rodion Podavalov。Artyom 训练非常刻苦，虽然在最初的几天里他可能会输给镇上的任何人，但现在他是最棒的，可以击败所有人。

他的哥哥 Rodion 以前拥有很高的技术，但他对 ACM 竞赛的沉迷压倒了他对乒乓球的热情，现在他把所有的空闲时间都花在了大学里。因此，他的体育能力现在保持在相同的水平。

但是，尽管有传言说 Rodion 影响了 Artyom 的发挥，Artyom 还是不想和除 Rodion 以外的任何人搭档。Artyom 相信数据，因此 Pavel Petrovich 决定寻求他在理工学院的朋友 Apollon Vladimirovich 的帮助，以说服 Artyom 相信他的搭档带来了不良影响。Apollon 认真地接受了这项任务，并提出了一个随机模型。他建议将乒乓球技术的值衡量为战胜随机对手的概率 $0 \le p \le 1$。

双人组合的获胜概率还取决于选手之间的相对魅力（第二名选手相对于第一名选手）$0 \le \alpha \le 1$，且等于 $q = p_1 \cdot (1 - \alpha) + p_2 \cdot \alpha$，其中 $p_1$ 和 $p_2$ 分别是第一名和第二名选手（即 Artyom 和 Rodion）的技术水平。Apollon 假设 Artyom 在第一场比赛中的技术水平为 $0$，在最后一场比赛中变为 $1$，并且在比赛过程中没有下降。Rodion 的技术水平以及他的相对魅力是恒定的。

给定这对双人组合在比赛中的胜负记录，你需要使用极大似然估计来找到这些恒定的值。更具体地，你需要找到值 $p_2$ 和 $\alpha$，使得存在一个非降的 Artyom 技术水平序列（从 $0$ 开始，到 $1$ 结束），使得乘积 $P_1 \cdot P_2 \cdots P_N$ 最大，其中 $P_i$ 是第 $i$ 场比赛已知结果的概率。该乘积是在所有可能的 $0 \le p_2, \alpha \le 1$ 以及所有可能的、首项为 $0$ 且末项（第 $N$ 项）为 $1$ 的 $N$ 个 Artyom 技术水平的非降序列中取最大值。

输入格式

第一行输入包含一个整数 $N$：记录中的比赛场数（$2 \le N \le 10^6$）。

第二行包含 $N$ 个整数，表示比赛结果：如果第 $i$ 场比赛输了，序列中的第 $i$ 个数为 $0$，否则为 $1$。

输出格式

你需要输出两个数，绝对或相对误差在 $10^{-9}$ 以内：Rodion 的技术水平和他的相对魅力。如果其中某些数值无法唯一确定，则输出 -1 代替该数值。

样例

输入样例 1

3
1 0 0

输出样例 1

0.3333333333 1.0000000000

输入样例 2

7
1 0 1 0 1 1 0

输出样例 2

0.6000000000 0.8333333333

输入样例 3

2
0 1

输出样例 3

-1 0