年轻的 Mirka 是一位业余音乐家。她演奏一种“多重钢琴”（multi-piano）。多重钢琴由无限个“多重琴键”（multi-keys）组成，这些琴键用可以解释为音高的整数表示。一首“多重乐曲”（为多重钢琴创作的乐曲）可以用一个有限的整数数组表示，其中整数表示演奏该乐曲时需要按下的多重琴键的顺序。

年轻的 Mirka 在“多重广播”（multi-radio）上听到了一首多重乐曲，现在她想演奏它。不幸的是，她无法准确听出按下了哪个琴键，但她能听出当前按下的琴键比前一个弹奏的琴键是更高、更低还是相同（更高的琴键用更大的数字表示）。因此，她决定按以下方式演奏这首乐曲：

• 在演奏之前，她会选择一个非负整数 $K$。
• 最开始，她会弹奏正确的第一个琴键（她的多重老师告诉了她这是哪个琴键）。
• 当她听到乐曲中当前弹奏的琴键比乐曲中前一个弹奏的琴键更高时，她将弹奏比她上一次弹奏的琴键大 $K$ 的琴键。
• 类似地，当她听到乐曲中当前弹奏的琴键比乐曲中前一个弹奏的琴键更低时，她将弹奏比她上一次弹奏的琴键小 $K$ 的琴键。
• 当她听到乐曲中当前弹奏的琴键与乐曲中前一个弹奏的琴键相同时，她将重复弹奏她上一次弹奏的琴键。

请注意，Mirka 在演奏时，并不会将自己弹奏的琴键音高与乐曲中的实际音高进行对比。

请帮助 Mirka 选择一个整数 $K$，使得她能够弹对尽可能多的琴键。

输入格式

第一行包含一个整数 $N$（$2 \le N \le 10^6$），表示广播中多重乐曲的琴键总数。

第二行包含 $N$ 个整数 $a_i$（$-10^9 \le a_i \le 10^9$），表示多重乐曲中依次弹奏的琴键。

输出格式

第一行输出 Mirka 最多可以弹对的琴键数量。

第二行输出一个非负整数 $K$，表示 Mirka 应该选择的参数，以达到最大正确数量。该数字必须小于或等于 $2 \cdot 10^9$。

请注意：满足要求的 $K$ 可能不唯一，但在给定的约束条件下一定存在。

样例

输入样例 1

5
1 2 0 3 1

输出样例 1

3
2

说明 1

Mirka 将依次弹奏以下琴键：1, 3, 1, 3, 1。加粗表示她弹奏正确的琴键。

输入样例 2

7
2 1 -6 -2 1 6 10

输出样例 2

5
4

说明 2

Mirka 将依次弹奏以下琴键：2, -2, -6, -2, 2, 6, 10。加粗表示她弹奏正确的琴键。