{"problem":{"name":"[JOI 2023 Final] 石子排列 2 / Stone Arranging 2","description":{"content":"JOI-kun has $N$ go stones. The stones are numbered from $1$ to $N$. The color of each stone is an integer between $1$ and $10^9$, inclusive. In the beginning, the color of Stone $i$ ($1 \\le i \\le N$) ","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9349"},"statements":[{"statement_type":"Markdown","content":"JOI-kun has $N$ go stones. The stones are numbered from $1$ to $N$. The color of each stone is an integer between $1$ and $10^9$, inclusive. In the beginning, the color of Stone $i$ ($1 \\le i \\le N$) is $A_i$.\n\nFrom now, JOI-kun will perform $N$ operations. He will put the stones on the table in a line. The operation $i$ ($1 \\le i \\le N$) will be performed as follows:\n\n1. JOI-kun will put Stone $i$ on the immediate right of Stone $i - 1$. However, when $i = 1$, JOI-kun will put Stone 1 on the table.\n2. If there is a stone among Stones $1,2,\\cdots,i-1$ whose current color is the same as Stone $i$, let $j$ be the maximum index of such stones, and JOI-kun will paint all of Stones $j+1,j+2,\\cdots,i-1$ with the color $A_i$.\n\nIn order to confirm whether the operations are correctly performed, JOI-kun wants to know in advance the colors of the stones after all the operations are performed.\n\nGiven information of the go stones, write a program which determines the colors of the stones after the $N$ operations are performed.\n\n## Input\n\nRead the following data from the standard input.\n\n> $N$  \n> $A_1$  \n> $A_2$  \n> $\\vdots$  \n> $A_N$\n\n## Output\n\nWrite $N$ lines to the standard output. The $i$-th line ($1 \\le i \\le N$) should contain the color of Stone $i$ after the $N$ operations are performed.\n\n[samples]\n\n## Note\n\n## Samples\n\n### Sample 1\n\nThe operations are performed as in the following table.\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/0newqhzt.png)\n\nFinally, the colors of Stones 1, 2, 3, 4, 5, 6 will be 1, 1, 1, 2, 2, 2, respectively.\n\nThis sample input satisfies the constraints of Subtasks 1, 3.\n\n### Sample 2\n\nThis sample input satisfies the constraints of all the subtasks.\n\n## Constraints\n\n- $1 \\le N \\le 2\\times 10^5$.\n- $1 \\le A_i \\le 10^9$ ($1 \\le i \\le N$).\n- Given values are all integers.\n\n## Subtasks\n\n1. (25 points) $N \\le 2 000$.\n2. (35 points) $A_i \\le 2$ ($1 \\le i \\le N$).\n3. (40 points) No additional constraints.","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9349","tags":["模拟","线段树","2023","JOI（日本）"],"sample_group":[["6\n1\n2\n1\n2\n3\n2\n","1\n1\n1\n2\n2\n2\n"],["10\n1\n1\n2\n2\n1\n2\n2\n1\n1\n2\n","1\n1\n1\n1\n1\n1\n1\n1\n1\n2\n"]],"created_at":"2026-03-03 11:09:25"}}