{"problem":{"name":"Movie Theater","description":{"content":"You are given a positive integer $N$ and sequences of positive integers of length $N$: $L=(L_1,L_2,\\ldots,L_N),R=(R_1,R_2,\\ldots,R_N)$. It is guaranteed that $L_1,L_2,\\ldots,L_N,R_1,R_2,\\ldots,R_N$ ar","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc200_c"},"statements":[{"statement_type":"Markdown","content":"You are given a positive integer $N$ and sequences of positive integers of length $N$: $L=(L_1,L_2,\\ldots,L_N),R=(R_1,R_2,\\ldots,R_N)$. It is guaranteed that $L_1,L_2,\\ldots,L_N,R_1,R_2,\\ldots,R_N$ are all distinct.\nA movie theater has $N$ seats arranged in a row from left to right. The $i$\\-th seat from the left is called seat $i$.\n$N$ people, numbered $1$ to $N$, visit this movie theater. You assign one seat to each person. Let $P_i$ be the seat assigned to person $i$. Then, person $i$ arrives at time $L_i$, crosses seats $1,2,\\ldots,P_i-1$ to sit in seat $P_i$, and leaves at time $R_i$, crossing seats $1,2,\\ldots,P_i-1$ to exit.\nThe **dissatisfaction** of person $i$ is the number of times other people cross seat $P_i$ during the time interval from time $L_i$ to time $R_i$ (not including exactly $L_i$ and $R_i$).\nFind the lexicographically smallest permutation $P$ of $(1,2,\\ldots,N)$ that minimizes the total dissatisfaction of all people from $1$ to $N$.\nYou are given $T$ test cases, so find the answer for each.\n\n## Constraints\n\n*   $1\\le T\\le 500$\n*   $1\\le N\\le 500$\n*   $1\\le L_i < R_i\\le 2\\times N$\n*   $L_1,L_2,\\ldots,L_N,R_1,R_2,\\ldots,R_N$ are all distinct.\n*   The sum of $N$ over all test cases is at most $500$.\n*   All input values are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$T$\n$\\text{case}_1$\n$\\text{case}_2$\n$\\vdots$\n$\\text{case}_T$\n\nEach test case is given in the following format:\n\n$N$\n$L_1$ $R_1$\n$L_2$ $R_2$\n$\\vdots$\n$L_N$ $R_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc200_c","tags":[],"sample_group":[["3\n3\n1 5\n2 3\n4 6\n4\n1 5\n2 6\n3 7\n4 8\n6\n6 10\n2 11\n7 8\n1 9\n3 4\n5 12","2 1 3\n1 2 3 4\n2 4 1 5 3 6\n\nFor the first test case, if we set $P=(2,1,3)$, the process proceeds as follows:\n\n*   Time $1$: Person $1$ sits in seat $2$.\n*   Time $2$: Person $2$ sits in seat $1$.\n*   Time $3$: Person $2$ leaves seat $1$.\n*   Time $4$: Person $3$ sits in seat $3$. Person $1$'s dissatisfaction increases by $1$.\n*   Time $5$: Person $1$ leaves seat $2$.\n*   Time $6$: Person $3$ leaves seat $3$.\n\nThe total dissatisfaction of all people in this case is $1$.\nIt is impossible to make the total dissatisfaction smaller than $1$, and furthermore, $P=(2,1,3)$ is lexicographically smallest among all $P$ with total dissatisfaction of $1$. Therefore, $P=(2,1,3)$ is the answer.\nFor the second test case, the total dissatisfaction of all people is $6$ for any permutation $P$."]],"created_at":"2026-03-03 11:01:14"}}