You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

小 Z 要学习弹钢琴了，但是他不太能找准音，所以他只能使用一种特殊技巧。

这里有一段“音乐”，音乐的长度为 $n$，里面的标准音由一段数字 $a_i$ 组成。

小 Z 能准确地弹出第一个标准音 $a_1$（然而也是老师教的），接下来他会确定好一个 $k$ 值， 此后如果要弹的标准音比上一个标准音高 $a_i>a_{i-1}$（数值大），小 Z 就会将自己的音升高 $k$；如果更低，会降低 $k$；如果相同，就不变。

问小 Z 确定一个多大的非负数 $k$，能使他弹对的音最多，输出最多的个数，再输出 $k$（有多个 $k$ 值时输出最小的）。

输入格式

从 piano.in 文件读入数据。

第一行一个正整数 $n$ 表示音乐的长度。

接下来一行 $n$ 个数，$a_1,a_2,\cdots,a_n$ 表示标准音。

输出格式

输出到 piano.out 文件。

第一行一个整数，表示最多能弹对的音的数量。

第二行一个整数，表示最小的 $k$ 值。

样例

5
1 2 0 3 1

3
1

7
2 1 -6 -2 1 6 10

5
4

样例3

此样例满足 $70\%$ 的数据点限制。

点击链接 ex_piano3.in 和 ex_piano3.out 下载大样例 3 的输入数据和输出数据。

样例4

此样例满足 $100\%$ 的数据点限制。

点击链接 ex_piano4.in 和 ex_piano4.out 下载大样例 4 的输入数据和输出数据。

说明/提示

样例 1 解释

小 Z 弹出的音用 $b_1,b_2,\cdots,b_n$ 表示。

当 $k = 1$ 时：

首先，$b_1=a_1=1$；因为 $a_2>a_1$，所以小 Z 弹出的音增加 $k$，得到 $b_2=2$；因为 $a_3<a_2$，小 Z 弹出的音减少 $k$，得到 $b_3=1$；因为 $a_4>a_3$，小 Z 弹出的音增加 $k$，得到 $b_4=2$；因为 $a_5<a_4$，小 Z 弹出的音减少 $k$，得到 $b_5=1$。

于是，得到 $b=[1,2,1,2,1]$，有 $b_1=a_1,b_2=a_2,b_5=a_5$，共有 $3$ 个音是弹对的。

虽然，当 $k=2$ 时，容易得到 $b=[1,3,1,3,1]$，此时也能弹对 $3$ 个，但是要求最小的 $k$。

数据范围

$30\%$ 的数据 $n \le 10^3$。

$50\%$ 的数据 $n \le 10^4$。

$70\%$ 的数据 $n \le 10^5$。

$100\%$ 的数据 $n \le 10^6,-2 \times 10 ^9 \le a_i \le 2 \times 10^9$。