{"problem":{"name":"LIS to Original Sequence","description":{"content":"Given are an integer $N$ and a monotonically increasing sequence of $K$ integers $A=(A_1,A_2,\\cdots,A_K)$. Find the **lexicographically smallest** permutation $P$ of $(1,2,\\cdots,N)$ that satisfies th","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc125_c"},"statements":[{"statement_type":"Markdown","content":"Given are an integer $N$ and a monotonically increasing sequence of $K$ integers $A=(A_1,A_2,\\cdots,A_K)$. Find the **lexicographically smallest** permutation $P$ of $(1,2,\\cdots,N)$ that satisfies the following condition.\n\n*   $A$ is a longest increasing subsequence of $P$ (a monotonically increasing subsequence of $P$ with the maximum possible length). It is fine if $P$ has multiple longest increasing subsequences, one of which is $A$.\n\nFrom the Constraints of this problem, we can prove that there always exists a $P$ that satisfies the condition.\n\n## Constraints\n\n*   $1 \\leq K \\leq N \\leq 2 \\times 10^5$\n*   $1 \\leq A_1 < A_2 < \\cdots < A_K \\leq N$\n*   All values in input are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $K$\n$A_1$ $A_2$ $\\cdots$ $A_K$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc125_c","tags":[],"sample_group":[["3 2\n2 3","2 1 3\n\n$A$ is a longest increasing subsequence of $P$ when $P=(2,1,3),(2,3,1)$. The answer is the lexicographically smallest of the two, or $(2,1,3)$."],["5 1\n4","5 4 3 2 1"]],"created_at":"2026-03-03 11:01:14"}}