English · Original
Chinese · Translation
Formal · Original
After one of celebrations there is a stack of dirty plates in Nikita's kitchen. Nikita has to wash them and put into a dryer. In dryer, the plates should be also placed in a stack also, and the plates sizes should increase down up. The sizes of all plates are distinct.
Nikita has no so much free space, specifically, he has a place for only one more stack of plates. Therefore, he can perform only such two operations:
* Take any number of plates from 1 to _a_ from the top of the dirty stack, wash them and put them to the _intermediate_ stack.
* Take any number of plates from 1 to _b_ from the top of the intermediate stack and put them to the stack in the dryer.
Note that after performing each of the operations, the plates are put in the same order as they were before the operation.
You are given the sizes of the plates _s_1, _s_2, ..., _s__n_ in the down up order in the dirty stack, and integers _a_ and _b_. All the sizes are distinct. Write a program that determines whether or not Nikita can put the plates in increasing down up order in the dryer. If he is able to do so, the program should find some sequence of operations (not necessary optimal) to achieve it.
## Input
The first line contains three integers _n_, _a_ and _b_ (1 ≤ _n_ ≤ 2000, 1 ≤ _a_, _b_ ≤ _n_). The second line contains integers _s_1, _s_2, ..., _s__n_ (1 ≤ _s__i_ ≤ _n_) — the sizes of the plates in down up order. All the sizes are distinct.
## Output
In the first line print "_YES_" if there is a solution. In this case, in the second line print integer _k_ — the number of operations. Then in _k_ lines print the operations, one per line. Each operation is described by two integers _t__j_ and _c__j_, where _t__j_ = 1, if the operation is to wash the top _c__j_ places from the dirty stack and put them onto the intermediate stack, and _t__j_ = 2, if the operation is to move th top _c__j_ plates from the intermediate stack to the dryer.
In case there is no solution, print single line "_NO_".
If there are multiple solutions, print any of them. Note that it is not necessary to minimize the number of operations.
[samples]
## Note
In the first example the initial order of plates was 2, 3, 6, 4, 1, 5. Here is how the stacks look like after each of the operations:
* \[1 2\]: Dirty stack: 6, 4, 1, 5. Intermediary stack: 2, 3. The dryer is empty.
* \[1 1\]: Dirty stack: 4, 1, 5. Intermediary stack: 6, 2, 3. The dryer is empty.
* \[2 1\]: Dirty stack: 4, 1, 5. Intermediary stack: 2, 3. Dryer stack: 6.
* \[1 2\]: Dirty stack: 5. Intermediary stack: 4, 1, 2, 3. Dryer stack: 6.
* \[1 1\]: There are no dirty plates. Intermediary stack: 5, 4, 1, 2, 3. Dryer stack: 6.
* \[2 1\]: There are no dirty plates. Intermediary stack: 4, 1, 2, 3. Dryer stack: 5, 6.
* \[2 1\]: There are no dirty plates. Intermediary stack: 1, 2, 3. Dryer stack: 4, 5, 6.
* \[2 3\]: All the plates are in the dryer: 1, 2, 3, 4, 5, 6.
In the second example it is possible to wash all the plates in one operation, and then move them all to the dryer.This is not possible in the third example, because it is not permitted to move more than one plate at the same time. It is possible to wash plates one by one so that they are placed onto the intermediary stack in the reverse order, and then move plates one by one to the dryer. The final order is correct.
在一次庆祝活动后，尼基塔的厨房里有一堆脏盘子。尼基塔需要洗盘子并把它们放进烘干机。在烘干机中，盘子也必须堆叠成一摞，且盘子的尺寸应从下到上递增。所有盘子的尺寸互不相同。
尼基塔的空间非常有限，具体来说，他只有一个额外的堆叠位置。因此，他只能执行以下两种操作：
注意，每次操作后，盘子的顺序与操作前保持一致。
给定脏堆中盘子的尺寸序列 #cf_span[s1, s2, ..., sn]（从下到上），以及两个整数 #cf_span[a] 和 #cf_span[b]。所有尺寸互不相同。编写一个程序，判断尼基塔是否能将盘子按从下到上递增的顺序放入烘干机。如果可以，程序应找出一个可行的操作序列（不一定是最优的）。
第一行包含三个整数 #cf_span[n], #cf_span[a] 和 #cf_span[b]（#cf_span[1 ≤ n ≤ 2000], #cf_span[1 ≤ a, b ≤ n]）。第二行包含整数 #cf_span[s1, s2, ..., sn]（#cf_span[1 ≤ si ≤ n]）——从下到上排列的盘子尺寸。所有尺寸互不相同。
如果存在解，第一行输出 "_YES_"。此时，第二行输出整数 #cf_span[k] —— 操作次数。接下来 #cf_span[k] 行，每行输出一个操作，用两个整数 #cf_span[tj] 和 #cf_span[cj] 描述：若 #cf_span[tj = 1]，表示将脏堆顶部的 #cf_span[cj] 个盘子洗下并放到中间堆；若 #cf_span[tj = 2]，表示将中间堆顶部的 #cf_span[cj] 个盘子移到烘干机。
如果无解，仅输出一行 "_NO_"。
若有多个解，输出任意一个即可。注意，无需最小化操作次数。
在第一个例子中，初始盘子顺序为 #cf_span[2, 3, 6, 4, 1, 5]。以下是每次操作后各堆的状态：
在第三个例子中，这是不可能的，因为不允许一次移动超过一个盘子。但可以逐个洗盘子，使它们以相反顺序放入中间堆，再逐个移入烘干机，最终顺序是正确的。
## Input
第一行包含三个整数 #cf_span[n], #cf_span[a] 和 #cf_span[b]（#cf_span[1 ≤ n ≤ 2000], #cf_span[1 ≤ a, b ≤ n]）。第二行包含整数 #cf_span[s1, s2, ..., sn]（#cf_span[1 ≤ si ≤ n]）——从下到上排列的盘子尺寸。所有尺寸互不相同。
## Output
第一行输出 "_YES_"（如果存在解）。此时，第二行输出整数 #cf_span[k] —— 操作次数。接下来 #cf_span[k] 行，每行输出一个操作，用两个整数 #cf_span[tj] 和 #cf_span[cj] 描述：若 #cf_span[tj = 1]，表示将脏堆顶部的 #cf_span[cj] 个盘子洗下并放到中间堆；若 #cf_span[tj = 2]，表示将中间堆顶部的 #cf_span[cj] 个盘子移到烘干机。如果无解，仅输出一行 "_NO_"。若有多个解，输出任意一个即可。注意，无需最小化操作次数。
[samples]
## Note
在第一个例子中，初始盘子顺序为 #cf_span[2, 3, 6, 4, 1, 5]。以下是每次操作后各堆的状态：
[1 2]：脏堆：#cf_span[6, 4, 1, 5]。中间堆：#cf_span[2, 3]。烘干机为空。
[1 1]：脏堆：#cf_span[4, 1, 5]。中间堆：#cf_span[6, 2, 3]。烘干机为空。
[2 1]：脏堆：#cf_span[4, 1, 5]。中间堆：#cf_span[2, 3]。烘干机：#cf_span[6]。
[1 2]：脏堆：#cf_span[5]。中间堆：#cf_span[4, 1, 2, 3]。烘干机：#cf_span[6]。
[1 1]：脏堆为空。中间堆：#cf_span[5, 4, 1, 2, 3]。烘干机：#cf_span[6]。
[2 1]：脏堆为空。中间堆：#cf_span[4, 1, 2, 3]。烘干机：#cf_span[5, 6]。
[2 1]：脏堆为空。中间堆：#cf_span[1, 2, 3]。烘干机：#cf_span[4, 5, 6]。
[2 3]：所有盘子都在烘干机中：#cf_span[1, 2, 3, 4, 5, 6]。
在第二个例子中，可以一次性将所有盘子洗到中间堆，再一次性全部移入烘干机。
在第三个例子中，这是不可能的，因为不允许一次移动超过一个盘子。但可以逐个洗盘子，使它们以相反顺序放入中间堆，再逐个移入烘干机，最终顺序是正确的。
**Definitions**
Let $ n, a, b \in \mathbb{Z}^+ $ with $ 1 \leq n \leq 2000 $, $ 1 \leq a, b \leq n $.
Let $ S = (s_1, s_2, \dots, s_n) $ be a sequence of distinct integers with $ s_i \in \{1, 2, \dots, n\} $, representing plate sizes in **down-to-up** order in the dirty stack (i.e., $ s_1 $ is bottom, $ s_n $ is top).
Let $ D $ be the dryer stack (initially empty), and $ I $ be the intermediate stack (initially empty).
Both $ D $ and $ I $ are stacks (LIFO), with bottom-to-top order matching the physical stacking direction.
**Operations**
1. **Type 1**: Move the top $ c $ plates ($ 1 \leq c \leq a $) from the dirty stack to the intermediate stack.
- The plates are moved in order: the top plate becomes the new top of $ I $.
2. **Type 2**: Move the top $ c $ plates ($ 1 \leq c \leq b $) from the intermediate stack to the dryer stack.
- The plates are moved in order: the top plate of $ I $ becomes the new top of $ D $.
**Goal**
Determine if it is possible to achieve a dryer stack $ D $ such that plate sizes are in **strictly increasing order from bottom to top** (i.e., $ D = (1, 2, 3, \dots, n) $ in bottom-to-top order).
**Constraints**
- At any time, the number of plates moved in a single operation must satisfy:
- For Type 1: $ 1 \leq c \leq a $
- For Type 2: $ 1 \leq c \leq b $
- The dirty stack must be fully emptied.
- The intermediate stack must be fully emptied.
**Objective**
Output:
- “NO” if no valid sequence of operations exists.
- “YES”, followed by a sequence of operations (each as $ (t_j, c_j) $) that achieves $ D = (1, 2, \dots, n) $ bottom-to-top, if possible.
API Response (JSON)
{
"problem": {
"name": "F. Dirty plates",
"description": {
"content": "After one of celebrations there is a stack of dirty plates in Nikita's kitchen. Nikita has to wash them and put into a dryer. In dryer, the plates should be also placed in a stack also, and the plates",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF737F"
},
"statements": [
{
"statement_type": "Markdown",
"content": "After one of celebrations there is a stack of dirty plates in Nikita's kitchen. Nikita has to wash them and put into a dryer. In dryer, the plates should be also placed in a stack also, and the plates...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "在一次庆祝活动后，尼基塔的厨房里有一堆脏盘子。尼基塔需要洗盘子并把它们放进烘干机。在烘干机中，盘子也必须堆叠成一摞，且盘子的尺寸应从下到上递增。所有盘子的尺寸互不相同。\n\n尼基塔的空间非常有限，具体来说，他只有一个额外的堆叠位置。因此，他只能执行以下两种操作：\n\n注意，每次操作后，盘子的顺序与操作前保持一致。\n\n给定脏堆中盘子的尺寸序列 #cf_span[s1, s2, ..., sn]（从下到上...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n, a, b \\in \\mathbb{Z}^+ $ with $ 1 \\leq n \\leq 2000 $, $ 1 \\leq a, b \\leq n $. \nLet $ S = (s_1, s_2, \\dots, s_n) $ be a sequence of distinct integers with $ s_i \\in \\{1, 2, \\...",
"is_translate": false,
"language": "Formal"
}
]
}