{"problem":{"name":"LIS and Inversion","description":{"content":"You are given an integer sequence $A=(A_1,A_2,\\cdots,A_N)$ of length $N$. Here, it is guaranteed that $0 \\leq A_i < i$ for each $i$. The **score** and **cost** of a permutation $P=(P_1,P_2,\\cdots,P_N)","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc180_e"},"statements":[{"statement_type":"Markdown","content":"You are given an integer sequence $A=(A_1,A_2,\\cdots,A_N)$ of length $N$. Here, it is guaranteed that $0 \\leq A_i < i$ for each $i$.\nThe **score** and **cost** of a permutation $P=(P_1,P_2,\\cdots,P_N)$ of $(1,2,\\cdots,N)$ are defined as follows:\n\n*   The score of $P$ is the length of a longest increasing subsequence of $P$.\n*   The cost of $P$ is the number of integers $i$ ($1 \\leq i \\leq N$) that satisfy the following condition:\n    *   There are fewer than $A_i$ integers $j$ such that $j < i$ and $P_j > P_i$.\n\nFor each $k=1,2,\\cdots,N$, solve the following problem:\n\n*   Find the minimum cost of a permutation $P$ whose score is at least $k$.\n\n## Constraints\n\n*   $1 \\leq N \\leq 250000$\n*   $0 \\leq A_i < i$\n*   All input values are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$\n$A_1$ $A_2$ $\\cdots$ $A_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc180_e","tags":[],"sample_group":[["4\n0 1 2 1","0 0 1 3\n\nFor each $k$, a solution $P$ is as follows:\n\n*   $k=1$: If $P=(4,2,1,3)$, then $P$ has the score of $2$ and the cost of $0$.\n*   $k=2$: If $P=(4,3,1,2)$, then $P$ has the score of $2$ and the cost of $0$.\n*   $k=3$: If $P=(4,1,2,3)$, then $P$ has the score of $3$ and the cost of $1$.\n*   $k=4$: If $P=(1,2,3,4)$, then $P$ has the score of $4$ and the cost of $3$."],["3\n0 0 0","0 0 0"],["5\n0 1 2 3 4","0 1 2 3 4"],["11\n0 0 2 3 4 5 3 7 8 2 10","0 0 0 1 2 3 4 5 7 8 9"]],"created_at":"2026-03-03 11:01:14"}}