← 返回题目列表

Codeforces · 954/C

C. 矩阵步行

中文机器翻译题面 查看原题

有一个大小为 x × y 的矩阵 A,其中填充有整数。对于每个 $$i \in [1..x]$$、$$j \in [1..y]$$ Ai,j = y(i - 1) + j。显然,[1..xy] 中的每个整数在此矩阵中只出现一次。

你已经走过了这个矩阵中的一些路径。您的路径可以描述为访问过的单元格 a1、a2、... 的序列,表示您从包含数字 a1 的单元格开始,然后移动到包含数字 a2 的单元格,依此类推。

从位于第 i 行第 j 列的单元格(我们将此单元格表示为 (i, j)),您可以移至以下单元格之一:

1. (i + 1, j) — 仅当 i < x 时;
2. (i, j + 1) — 仅当 j < y;
3. (i - 1, j) — 仅当 i > 1 时;
4. (i, j - 1) — 仅当 j > 1 时。

请注意,进行移动需要您前往相邻的单元格。不允许呆在同一个牢房里。您并不确切知道 x 和 y,但您必须找到这些数字的任何可能值,以便您可以从包含整数 a1 的单元格开始,然后移动到包含 a2 的单元格(一步),然后移动到包含 a3 的单元格(同样一步),依此类推。你能选择 x 和 y 以使它们不与你的移动顺序相矛盾吗?

输入

第一行包含一个整数 n (1 ≤ n ≤ 200000) — 您在路径上访问过的单元格数量(如果某个单元格被访问两次,则它会列出两次)。

第二行包含 n 个整数 a1, a2, ..., an (1 ≤ ai ≤ 109) — 路径上单元格中的整数。

输出

如果 x 和 y 的所有可能值(例如 1 ≤ x, y ≤ 109)与有关路径的信息相矛盾,则打印 NO。

否则,在第一行中打印 YES,并在第二行中打印值 x 和 y,这样您的路径就可以在矩阵中具有如此数量的行和列。请记住,它们必须是不超过 109 的正整数。

示例

输入 #1

8
1 2 3 6 9 8 5 2

输出 #1

YES
3 3

输入 #2

6
1 2 1 2 5 3

输出 #2

NO

输入 #3

2
1 10

输出 #3

YES
4 9

注意

第一个测试中的矩阵及其路径如下所示:

第一个和第三个示例也存在多个正确答案。