{"problem":{"name":"[EC Final 2022] Inversion","description":{"content":"$\\textbf{This is an interactive problem.}$ There is a hidden permutation $p_1, p_2, \\dots, p_n$ of $\\{1, 2, \\dots, n\\}$. You want to find it by asking the parity of the number of inversions of $p_l,\\","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9721"},"statements":[{"statement_type":"Markdown","content":"$\\textbf{This is an interactive problem.}$\n\nThere is a hidden permutation $p_1, p_2, \\dots, p_n$ of $\\{1, 2, \\dots, n\\}$. You want to find it by asking the parity of the number of inversions of $p_l,\\ldots, p_r$.\n\nYou can query in the format ${?~l~r}$, and the interactor will respond you $\\left( \\sum_{l\\leq i < j\\leq r} [p_i > p_j]\\right) \\bmod 2$. $[p_i>p_j]$ is $1$ when $p_i>p_j$ and $0$ when $p_i\\le p_j$.\n\n## Input\n\nFirstly, you should read the integer $n$ ($1\\le n\\le 2000$).\n\nAfter that, you can make no more than $4 \\times 10^4$ queries. To make a query, output ``${?~l~r}$'' ($1 \\leq l \\leq r \\leq n$) on a separate line, then you should read the response from standard input. \n\nTo give your answer, print ``${!~p_1~p_2~\\dots~p_n}$'' on a separate line. The output of the answer is \\textbf{not} counted towards the limit of $4 \\times 10^4$ queries. \n\nAfter that, your program should terminate. \n\nAfter printing a query, do not forget to output end of line and flush the output. To do this, use $\\texttt{fflush(stdout)}$ or $\\texttt{cout.flush()}$ in C++, $\\texttt{System.out.flush()}$ in Java, $\\texttt{flush(output)}$ in Pascal, or $\\texttt{stdout.flush()}$ in Python. \n\nIt is guaranteed that the permutation is fixed in advance. \n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9721","tags":["二分","2022","交互题","Special Judge","O2优化","排序","ICPC","EC Final"],"sample_group":[["3\n\n0\n\n0\n\n1\n","\n? 1 2\n\n? 1 3\n\n? 2 3\n\n! 2 3 1"]],"created_at":"2026-03-03 11:09:25"}}