English · Original
Chinese · Translation
Formal · Original
_This is an interactive problem. Refer to the Interaction section below for better understanding._
Ithea and Chtholly want to play a game in order to determine who can use the kitchen tonight.
<center>
</center>Initially, Ithea puts _n_ clear sheets of paper in a line. They are numbered from 1 to _n_ from left to right.
This game will go on for _m_ rounds. In each round, Ithea will give Chtholly an integer between 1 and _c_, and Chtholly needs to choose one of the sheets to write down this number (if there is already a number before, she will erase the original one and replace it with the new one).
Chtholly wins if, at any time, all the sheets are filled with a number and the _n_ numbers are in non-decreasing order looking from left to right from sheet 1 to sheet _n_, and if after _m_ rounds she still doesn't win, she loses the game.
Chtholly really wants to win the game as she wants to cook something for Willem. But she doesn't know how to win the game. So Chtholly finds you, and your task is to write a program to receive numbers that Ithea gives Chtholly and help her make the decision on which sheet of paper write this number.
## Input
The first line contains 3 integers _n_, _m_ and _c_ (, means rounded up) — the number of sheets, the number of rounds and the largest possible number Ithea can give to Chtholly respectively. The remaining parts of input are given throughout the interaction process.
## Interaction
In each round, your program needs to read one line containing a single integer _p__i_ (1 ≤ _p__i_ ≤ _c_), indicating the number given to Chtholly.
Your program should then output a line containing an integer between 1 and _n_, indicating the number of sheet to write down this number in.
**After outputting each line, don't forget to flush the output.** For example:
* _fflush(stdout)_ in C/C++;
* _System.out.flush()_ in Java;
* _sys.stdout.flush()_ in Python;
* _flush(output)_ in Pascal;
* See the documentation for other languages.
**If Chtholly wins at the end of a round, no more input will become available and your program should terminate normally.** It can be shown that under the constraints, it's always possible for Chtholly to win the game.
[samples]
## Note
In the example, Chtholly initially knew there were 2 sheets, 4 rounds and each number was between 1 and 4. She then received a 2 and decided to write it in the 1st sheet. Then she received a 1 and wrote it in the 2nd sheet. At last, she received a 3 and replaced 1 with 3 in the 2nd sheet. At this time all the sheets were filled with a number and they were non-decreasing, so she won the game.
**Note that it is required that your program terminate immediately after Chtholly wins and do not read numbers from the input for the remaining rounds. If not, undefined behaviour may arise and it won't be sure whether your program will be accepted or rejected. Also because of this, please be careful when hacking others' codes.** In the sample, Chtholly won the game after the 3rd round, so it is required that your program doesn't read the number of the remaining 4th round.
The input format for hacking:
* The first line contains 3 integers _n_, _m_ and _c_;
* The following _m_ lines each contains an integer between 1 and _c_, indicating the number given to Chtholly in each round.
_这是一个交互式问题。请参阅下面的交互部分以获得更好的理解。_
Ithea 和 Chtholly 想玩一个游戏，以决定今晚谁可以使用厨房。
最初，Ithea 在一条直线上放置了 #cf_span[n] 张空白纸张。它们从左到右编号为 #cf_span[1] 到 #cf_span[n]。
这个游戏将持续 #cf_span[m] 轮。在每一轮中，Ithea 会给出 Chtholly 一个介于 #cf_span[1] 和 #cf_span[c] 之间的整数，Chtholly 需要选择一张纸，将这个数字写在上面（如果之前已经有数字，她会擦除原来的数字并用新数字替换）。
如果在任意时刻，所有纸张都被填满数字，并且从左到右（从第 #cf_span[1] 张纸到第 #cf_span[n] 张纸）的 #cf_span[n] 个数字呈非递减顺序，则 Chtholly 获胜；如果在 #cf_span[m] 轮结束后她仍未获胜，则她输掉游戏。
Chtholly 非常想赢得游戏，因为她想为 Willem 做点吃的。但她不知道如何获胜。于是 Chtholly 找到了你，你的任务是编写一个程序，接收 Ithea 给 Chtholly 的数字，并帮助她决定将这个数字写在哪张纸上。
第一行包含三个整数 #cf_span[n, m] 和 #cf_span[c]（, 表示向上取整）— 分别为纸张数量、轮数以及 Ithea 可以给出 Chtholly 的最大数字。输入的其余部分在交互过程中给出。
在每一轮中，你的程序需要读取一行，包含一个整数 #cf_span[pi]（#cf_span[1 ≤ pi ≤ c]），表示 Ithea 给出的数字。
然后你的程序应输出一行，包含一个介于 #cf_span[1] 和 #cf_span[n] 之间的整数，表示将该数字写入的纸张编号。
*每次输出后，请不要忘记刷新输出。* 例如：
*如果 Chtholly 在某一轮结束时获胜，则不会再有输入，你的程序应正常终止。* 可以证明，在给定约束下，Chtholly 总是可以获胜。
在示例中，Chtholly 最初知道有 #cf_span[2] 张纸、#cf_span[4] 轮，且每个数字介于 #cf_span[1] 和 #cf_span[4] 之间。她随后收到了一个 #cf_span[2]，并决定将其写在第 #cf_span[1] 张纸上。接着她收到了一个 #cf_span[1]，并将其写在第 #cf_span[2] 张纸上。最后，她收到了一个 #cf_span[3]，并将第 #cf_span[2] 张纸上的 #cf_span[1] 替换为 #cf_span[3]。此时所有纸张都被填满，且数字呈非递减顺序，因此她赢得了游戏。
*请注意，一旦 Chtholly 获胜，你的程序必须立即终止，不再读取后续轮次的输入。否则，可能产生未定义行为，无法保证你的程序会被接受或拒绝。此外，由于这一点，请在 hack 其他人的代码时格外小心。* 在示例中，Chtholly 在第 #cf_span[3] 轮后获胜，因此你的程序不应读取第 #cf_span[4] 轮的剩余数字。
黑客输入格式：
## Input
第一行包含三个整数 #cf_span[n, m] 和 #cf_span[c]（, 表示向上取整）— 分别为纸张数量、轮数以及 Ithea 可以给出 Chtholly 的最大数字。输入的其余部分在交互过程中给出。
## Interaction
在每一轮中，你的程序需要读取一行，包含一个整数 #cf_span[pi]（#cf_span[1 ≤ pi ≤ c]），表示 Ithea 给出的数字。你的程序应输出一行，包含一个介于 #cf_span[1] 和 #cf_span[n] 之间的整数，表示将该数字写入的纸张编号。*每次输出后，请不要忘记刷新输出。* 例如： _fflush(stdout)_ 在 C/C++ 中； _System.out.flush()_ 在 Java 中； _sys.stdout.flush()_ 在 Python 中； _flush(output)_ 在 Pascal 中； 请参阅其他语言的文档。 *如果 Chtholly 在某一轮结束时获胜，则不会再有输入，你的程序应正常终止。* 可以证明，在给定约束下，Chtholly 总是可以获胜。
[samples]
## Note
在示例中，Chtholly 最初知道有 #cf_span[2] 张纸、#cf_span[4] 轮，且每个数字介于 #cf_span[1] 和 #cf_span[4] 之间。她随后收到了一个 #cf_span[2]，并决定将其写在第 #cf_span[1] 张纸上。接着她收到了一个 #cf_span[1]，并将其写在第 #cf_span[2] 张纸上。最后，她收到了一个 #cf_span[3]，并将第 #cf_span[2] 张纸上的 #cf_span[1] 替换为 #cf_span[3]。此时所有纸张都被填满，且数字呈非递减顺序，因此她赢得了游戏。 *请注意，一旦 Chtholly 获胜，你的程序必须立即终止，不再读取后续轮次的输入。否则，可能产生未定义行为，无法保证你的程序会被接受或拒绝。此外，由于这一点，请在 hack 其他人的代码时格外小心。* 在示例中，Chtholly 在第 #cf_span[3] 轮后获胜，因此你的程序不应读取第 #cf_span[4] 轮的剩余数字。黑客输入格式： 第一行包含三个整数 #cf_span[n, m] 和 #cf_span[c]； 接下来的 #cf_span[m] 行每行包含一个介于 #cf_span[1] 和 #cf_span[c] 之间的整数，表示每轮 Ithea 给出 Chtholly 的数字。
**Definitions**
Let $ n, m, c \in \mathbb{Z}^+ $ denote the number of sheets, number of rounds, and maximum value respectively, with $ m \geq \lceil \frac{n}{2} \rceil $.
Let $ P = (p_1, p_2, \dots, p_m) $ be the sequence of integers provided by Ithea, where $ p_i \in [1, c] $.
Let $ A = (a_1, a_2, \dots, a_n) $ be the current state of the sheets, initially $ a_i = \bot $ (undefined) for all $ i \in [1, n] $.
**Constraints**
1. $ 1 \leq n \leq 1000 $, $ 1 \leq c \leq 10^9 $, $ m \geq \lceil \frac{n}{2} \rceil $.
2. For each round $ i \in [1, m] $: $ 1 \leq p_i \leq c $.
3. Chtholly wins if at any round $ i $: $ a_j \neq \bot $ for all $ j \in [1, n] $ and $ a_1 \leq a_2 \leq \dots \leq a_n $.
**Objective**
For each round $ i \in [1, m] $:
- Read $ p_i $.
- Output an index $ j \in [1, n] $ indicating the sheet to write $ p_i $ on.
- Update $ a_j \leftarrow p_i $.
- If $ A $ becomes non-decreasing and fully filled, terminate immediately.
**Strategy**
Maintain the array $ A $ and enforce non-decreasing order by:
- If $ p_i \leq \frac{c+1}{2} $, place it in the leftmost position $ j $ such that $ a_j > p_i $ or $ a_j = \bot $, scanning left to right.
- If $ p_i > \frac{c+1}{2} $, place it in the rightmost position $ j $ such that $ a_j < p_i $ or $ a_j = \bot $, scanning right to left.
This ensures the array remains sortable and converges to non-decreasing order.
API Response (JSON)
{
"problem": {
"name": "D. Ithea Plays With Chtholly",
"description": {
"content": "_This is an interactive problem. Refer to the Interaction section below for better understanding._ Ithea and Chtholly want to play a game in order to determine who can use the kitchen tonight. <cent",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 1000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF897D"
},
"statements": [
{
"statement_type": "Markdown",
"content": "_This is an interactive problem. Refer to the Interaction section below for better understanding._\n\nIthea and Chtholly want to play a game in order to determine who can use the kitchen tonight.\n\n<cent...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "_这是一个交互式问题。请参阅下面的交互部分以获得更好的理解。_\n\nIthea 和 Chtholly 想玩一个游戏，以决定今晚谁可以使用厨房。\n\n最初，Ithea 在一条直线上放置了 #cf_span[n] 张空白纸张。它们从左到右编号为 #cf_span[1] 到 #cf_span[n]。\n\n这个游戏将持续 #cf_span[m] 轮。在每一轮中，Ithea 会给出 Chtholly 一个介于 #...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n, m, c \\in \\mathbb{Z}^+ $ denote the number of sheets, number of rounds, and maximum value respectively, with $ m \\geq \\lceil \\frac{n}{2} \\rceil $. \nLet $ P = (p_1, p_2, \\dot...",
"is_translate": false,
"language": "Formal"
}
]
}