{"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 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.\n\nFrom 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:\n\n1.  (_i_ + 1, _j_) — only if _i_ < _x_;\n2.  (_i_, _j_ + 1) — only if _j_ < _y_;\n3.  (_i_ - 1, _j_) — only if _i_ > 1;\n4.  (_i_, _j_ - 1) — only if _j_ > 1.\n\nNotice 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?\n\n## Input\n\nThe 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).\n\nThe second line contains _n_ integers _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ 109) — the integers in the cells on your path.\n\n## Output\n\nIf all possible values of _x_ and _y_ such that 1 ≤ _x_, _y_ ≤ 109 contradict with the information about your path, print _NO_.\n\nOtherwise, 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.\n\n[samples]\n\n## Note\n\nThe matrix and the path on it in the first test looks like this:\n\n<center>![image](https://espresso.codeforces.com/190a823a508d8dcf4bd86277a5f22b80210849c6.png)</center>Also there exist multiple correct answers for both the first and the third examples.","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$ 的单元格，依此类推。\n\n从位于第 $i$ 行、第 $j$ 列的单元格（记作 $(i, j)$）出发，你可以移动到以下相邻单元格之一：\n\n注意，每次移动必须到达一个相邻的单元格，不允许停留在原地。你并不确切知道 $x$ 和 $y$ 的值，但你需要找出任意一组可能的 $x$ 和 $y$ 的值，使得你可以从包含整数 $a_1$ 的单元格出发，一步移动到包含 $a_2$ 的单元格，再一步移动到包含 $a_3$ 的单元格，依此类推。你能否选择 $x$ 和 $y$，使其与你的移动序列不矛盾？\n\n第一行包含一个整数 $n$ ($1 ≤ n ≤ 200000$) —— 你路径上访问的单元格数量（如果某个单元格被访问多次，则会重复列出）。\n\n第二行包含 $n$ 个整数 $a_1, a_2, ..., a_n$ ($1 ≤ a_i ≤ 10^9$) —— 路径上各单元格中的整数。\n\n如果所有满足 $1 ≤ x, y ≤ 10^9$ 的 $x$ 和 $y$ 的取值都与你的路径信息矛盾，请输出 _NO_。\n\n否则，第一行输出 _YES_，第二行输出两个值 $x$ 和 $y$，使得你的路径在具有如此行数和列数的矩阵中是可行的。请记住，它们必须是不超过 $10^9$ 的正整数。\n\n第一个测试用例中的矩阵和路径如下所示：\n\n此外，第一个和第三个示例都存在多个正确答案。\n\n## Input\n\n第一行包含一个整数 $n$ ($1 ≤ n ≤ 200000$) —— 你路径上访问的单元格数量（如果某个单元格被访问多次，则会重复列出）。第二行包含 $n$ 个整数 $a_1, a_2, ..., a_n$ ($1 ≤ a_i ≤ 10^9$) —— 路径上各单元格中的整数。\n\n## Output\n\n如果所有满足 $1 ≤ x, y ≤ 10^9$ 的 $x$ 和 $y$ 的取值都与你的路径信息矛盾，请输出 _NO_。否则，第一行输出 _YES_，第二行输出两个值 $x$ 和 $y$，使得你的路径在具有如此行数和列数的矩阵中是可行的。请记住，它们必须是不超过 $10^9$ 的正整数。\n\n[samples]\n\n## Note\n\n第一个测试用例中的矩阵和路径如下所示：  此外，第一个和第三个示例都存在多个正确答案。","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 dimensions $ x \\times y $, with $ x, y \\in \\mathbb{Z}^+ $, $ x, y \\leq 10^9 $, and entries defined by:  \n$$\nM[i,j] = y(i-1) + j, \\quad \\text{for } 1 \\leq i \\leq x, \\, 1 \\leq j \\leq y.\n$$\n\nEach integer $ a_k $ corresponds to a unique cell $ (i_k, j_k) $ such that:  \n$$\na_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.\n$$\n\n**Constraints**  \n1. $ 1 \\leq n \\leq 200000 $  \n2. $ 1 \\leq a_k \\leq 10^9 $ for all $ k \\in \\{1, \\dots, n\\} $  \n3. For all $ k \\in \\{1, \\dots, n-1\\} $, the cells $ (i_k, j_k) $ and $ (i_{k+1}, j_{k+1}) $ must be adjacent:  \n   $$\n   |i_k - i_{k+1}| + |j_k - j_{k+1}| = 1\n   $$\n\n**Objective**  \nFind 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.  \n\nIf no such $ (x, y) $ exists, output **NO**.  \nOtherwise, output **YES** followed by one valid pair $ (x, y) $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF954C","tags":["implementation"],"sample_group":[["8\n1 2 3 6 9 8 5 2","YES\n3 3"],["6\n1 2 1 2 5 3","NO"],["2\n1 10","YES\n4 9"]],"created_at":"2026-03-03 11:00:39"}}