English · Original
Chinese · Translation
Formal · Original
There is a matrix _A_ of size _x_ × _y_ filled with integers. For every , _A__i_, _j_ = _y_(_i_ - 1) + _j_. Obviously, every integer from \[1.._xy_\] occurs exactly once in this matrix.
You have traversed some path in this matrix. Your path can be described as a sequence of visited cells _a_1, _a_2, ..., _a__n_ denoting that you started in the cell containing the number _a_1, then moved to the cell with the number _a_2, and so on.
From the cell located in _i_\-th line and _j_\-th column (we denote this cell as (_i_, _j_)) you can move into one of the following cells:
1. (_i_ + 1, _j_) — only if _i_ < _x_;
2. (_i_, _j_ + 1) — only if _j_ < _y_;
3. (_i_ - 1, _j_) — only if _i_ > 1;
4. (_i_, _j_ - 1) — only if _j_ > 1.
Notice that making a move requires you to go to an adjacent cell. It is not allowed to stay in the same cell. You don't know _x_ and _y_ exactly, but you have to find any possible values for these numbers such that you could start in the cell containing the integer _a_1, then move to the cell containing _a_2 (in one step), then move to the cell containing _a_3 (also in one step) and so on. Can you choose _x_ and _y_ so that they don't contradict with your sequence of moves?
## Input
The first line contains one integer number _n_ (1 ≤ _n_ ≤ 200000) — the number of cells you visited on your path (if some cell is visited twice, then it's listed twice).
The second line contains _n_ integers _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ 109) — the integers in the cells on your path.
## Output
If all possible values of _x_ and _y_ such that 1 ≤ _x_, _y_ ≤ 109 contradict with the information about your path, print _NO_.
Otherwise, print _YES_ in the first line, and in the second line print the values _x_ and _y_ such that your path was possible with such number of lines and columns in the matrix. Remember that they must be positive integers not exceeding 109.
[samples]
## Note
The matrix and the path on it in the first test looks like this:
<center></center>Also there exist multiple correct answers for both the first and the third examples.
有一个大小为 $x × y$ 的矩阵 $A$，其中填满了整数。对于每个位置，$A_{i, j} = y(i - 1) + j$。显然，区间 $[1..xy]$ 中的每个整数在该矩阵中恰好出现一次。
你在这个矩阵中走了一条路径。你的路径可以用一系列访问的单元格 $a_1, a_2, ..., a_n$ 来描述，表示你从包含数字 $a_1$ 的单元格开始，然后移动到包含数字 $a_2$ 的单元格，依此类推。
从位于第 $i$ 行、第 $j$ 列的单元格（记作 $(i, j)$）出发，你可以移动到以下相邻单元格之一：
注意，每次移动必须到达一个相邻的单元格，不允许停留在原地。你并不确切知道 $x$ 和 $y$ 的值，但你需要找出任意一组可能的 $x$ 和 $y$ 的值，使得你可以从包含整数 $a_1$ 的单元格出发，一步移动到包含 $a_2$ 的单元格，再一步移动到包含 $a_3$ 的单元格，依此类推。你能否选择 $x$ 和 $y$，使其与你的移动序列不矛盾？
第一行包含一个整数 $n$ ($1 ≤ n ≤ 200000$) —— 你路径上访问的单元格数量（如果某个单元格被访问多次，则会重复列出）。
第二行包含 $n$ 个整数 $a_1, a_2, ..., a_n$ ($1 ≤ a_i ≤ 10^9$) —— 路径上各单元格中的整数。
如果所有满足 $1 ≤ x, y ≤ 10^9$ 的 $x$ 和 $y$ 的取值都与你的路径信息矛盾，请输出 _NO_。
否则，第一行输出 _YES_，第二行输出两个值 $x$ 和 $y$，使得你的路径在具有如此行数和列数的矩阵中是可行的。请记住，它们必须是不超过 $10^9$ 的正整数。
第一个测试用例中的矩阵和路径如下所示：
此外，第一个和第三个示例都存在多个正确答案。
## Input
第一行包含一个整数 $n$ ($1 ≤ n ≤ 200000$) —— 你路径上访问的单元格数量（如果某个单元格被访问多次，则会重复列出）。第二行包含 $n$ 个整数 $a_1, a_2, ..., a_n$ ($1 ≤ a_i ≤ 10^9$) —— 路径上各单元格中的整数。
## Output
如果所有满足 $1 ≤ x, y ≤ 10^9$ 的 $x$ 和 $y$ 的取值都与你的路径信息矛盾，请输出 _NO_。否则，第一行输出 _YES_，第二行输出两个值 $x$ 和 $y$，使得你的路径在具有如此行数和列数的矩阵中是可行的。请记住，它们必须是不超过 $10^9$ 的正整数。
[samples]
## Note
第一个测试用例中的矩阵和路径如下所示： 此外，第一个和第三个示例都存在多个正确答案。
**Definitions**
Let $ n \in \mathbb{Z} $ be the length of the path.
Let $ A = (a_1, a_2, \dots, a_n) $ be the sequence of integers visited, where $ a_i \in [1, 10^9] $.
The matrix $ M $ has dimensions $ x \times y $, with $ x, y \in \mathbb{Z}^+ $, $ x, y \leq 10^9 $, and entries defined by:
$$
M[i,j] = y(i-1) + j, \quad \text{for } 1 \leq i \leq x, \, 1 \leq j \leq y.
$$
Each integer $ a_k $ corresponds to a unique cell $ (i_k, j_k) $ such that:
$$
a_k = y(i_k - 1) + j_k \quad \Rightarrow \quad i_k = \left\lfloor \frac{a_k - 1}{y} \right\rfloor + 1, \quad j_k = (a_k - 1) \bmod y + 1.
$$
**Constraints**
1. $ 1 \leq n \leq 200000 $
2. $ 1 \leq a_k \leq 10^9 $ for all $ k \in \{1, \dots, n\} $
3. For all $ k \in \{1, \dots, n-1\} $, the cells $ (i_k, j_k) $ and $ (i_{k+1}, j_{k+1}) $ must be adjacent:
$$
|i_k - i_{k+1}| + |j_k - j_{k+1}| = 1
$$
**Objective**
Find any pair $ (x, y) \in \mathbb{Z}^+ \times \mathbb{Z}^+ $, $ x, y \leq 10^9 $, such that the above adjacency condition holds for all consecutive pairs in $ A $, **or** determine that no such pair exists.
If no such $ (x, y) $ exists, output **NO**.
Otherwise, output **YES** followed by one valid pair $ (x, y) $.
API Response (JSON)
{
"problem": {
"name": "C. Matrix Walk",
"description": {
"content": "There is a matrix _A_ of size _x_ × _y_ filled with integers. For every , _A__i_, _j_ = _y_(_i_ - 1) + _j_. Obviously, every integer from \\[1.._xy_\\] occurs exactly once in this matrix. You have trav",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 1000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF954C"
},
"statements": [
{
"statement_type": "Markdown",
"content": "There is a matrix _A_ of size _x_ × _y_ filled with integers. For every , _A__i_, _j_ = _y_(_i_ - 1) + _j_. Obviously, every integer from \\[1.._xy_\\] occurs exactly once in this matrix.\n\nYou have trav...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "有一个大小为 $x × y$ 的矩阵 $A$，其中填满了整数。对于每个位置，$A_{i, j} = y(i - 1) + j$。显然，区间 $[1..xy]$ 中的每个整数在该矩阵中恰好出现一次。\n\n你在这个矩阵中走了一条路径。你的路径可以用一系列访问的单元格 $a_1, a_2, ..., a_n$ 来描述，表示你从包含数字 $a_1$ 的单元格开始，然后移动到包含数字 $a_2$ 的单元格，依...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z} $ be the length of the path. \nLet $ A = (a_1, a_2, \\dots, a_n) $ be the sequence of integers visited, where $ a_i \\in [1, 10^9] $. \n\nThe matrix $ M $ has dim...",
"is_translate": false,
"language": "Formal"
}
]
}