---{"category_name":"easy","problem_code":"ATMQ","problem_name":"ATM Queue","problemComponents":{"constraints":"- $1 \\leq T \\leq 2 \\cdot 10^4$\n- $1 \\leq N \\leq 2 \\cdot 10^5$\n- $1 \\leq A_i \\leq N$\n- Sum of $N$ over all test cases doesn\u0027t exceed $2 \\cdot 10^5$.\n","constraintsState":true,"subtasks":"","subtasksState":true,"inputFormat":"- First line of input contains $T$, the number of test cases. Then $T$ test cases follow.\n- Each test case consists of two lines of input.\n- First line of each test case contains $N$, the number of people in the queue.\n- Second line of each test case contains $N$ positive integers $A_i$, the power level of $i^{th}$ person.\n","inputFormatState":true,"outputFormat":"For each test case, print a line containing $N$ numbers where $i^{th}$ number is equal to the time at which $i^{th}$ person uses the ATM.\n","outputFormatState":true,"sampleTestCases":{"0":{"id":1,"input":"3\n5\n2 3 4 1 5\n4\n1 2 4 2\n10\n5 1 3 7 6 9 8 9 2 10","output":"1 4 2 5 3\n1 3 2 4\n1 10 2 3 8 4 7 5 9 6","explanation":"**Test Case $1$:**\nInitially, let the order of people in the queue is $[1, 2, 3, 4, 5]$, and their power levels are $2, 3, 4, 1$ and $5$ respectively.\n- During the $1^{st}$ second, $1$ uses the ATM and leaves. The order of the people in the queue will be $[2, 3, 4, 5]$ after $1$ leaves. Now people start overtaking ($2^{nd}$ step of the process). Since $3$ is the $2^{nd}$ person in the queue and $2$ is in front of him and $A_2$ \u003C $A_3$, $3$ will overtake $2$. The order of the people in the queue will become $[3, 2, 4, 5]$. Now $4$ is the $3^{rd}$ person in the queue and $2$ is in front of him. But $A_2$ \u003E $A_4$, so there will be no overtaking here. Finally, $5$ is the $4^{th}$ person and $4$ is in front of him. And since $A_4$ \u003C $A_5$, $5$ will overtake $4$ and The order of the people in the queue will be $[3, 2, 5, 4]$ after the $1$st second.\n\n- During the $2^{nd}$ second, $3$ is in front of the queue. He will use the ATM and leave. The order of the people in the queue will become $[2, 5, 4]$. Since $5$ is the $2^{nd}$ person in the queue with $2$ in front of him and $A_2$ \u003C $A_5$, $5$ will overtake $2$ and the order of the people in the queue becomes $[5, 2, 4]$. Now $4$ is the $3^{rd}$ person in the queue. But $A_2$ \u003E $A_4$, so $4$ can\u0027t overtake $2$. By the end of $2^{nd}$ second, the order of people in the queue is $[5, 2, 4$].\n\n- During the $3^{rd}$ second, $5$ is in front of the queue. He will use the ATM and leave. After this, the queue will be $2, 4$. And since $A_2$ \u003E $A_4$, there will be no overtaking.\n\n- During the $4^{th}$ second, $2$ uses the ATM and leaves. \n\n- During the $5^{th}$ second, $4$ uses the ATM and leaves.\n\nHence, $1, 2, 3, 4$ and $5$ use the ATM at $1, 4, 2, 5, 3$ second, respectively.","isDeleted":false}}},"video_editorial_url":"https://youtu.be/J3sLunJA6gM","languages_supported":{"0":"CPP14","1":"C","2":"JAVA","3":"PYTH 3.6","4":"CPP17","5":"PYTH","6":"PYP3","7":"CS2","8":"ADA","9":"PYPY","10":"TEXT","11":"PAS fpc","12":"NODEJS","13":"RUBY","14":"PHP","15":"GO","16":"HASK","17":"TCL","18":"PERL","19":"SCALA","20":"LUA","21":"kotlin","22":"BASH","23":"JS","24":"LISP sbcl","25":"rust","26":"PAS gpc","27":"BF","28":"CLOJ","29":"R","30":"D","31":"CAML","32":"FORT","33":"ASM","34":"swift","35":"FS","36":"WSPC","37":"LISP clisp","38":"SQL","39":"SCM guile","40":"PERL6","41":"ERL","42":"CLPS","43":"ICK","44":"NICE","45":"PRLG","46":"ICON","47":"COB","48":"SCM chicken","49":"PIKE","50":"SCM qobi","51":"ST","52":"SQLQ","53":"NEM"},"max_timelimit":1,"source_sizelimit":50000,"problem_author":"akashbhalotia","problem_tester":"","date_added":"11-09-2021","tags":{"0":"akashbhalotia","1":"easy","2":"start11"},"problem_difficulty_level":"Unavailable","best_tag":"","editorial_url":"https://discuss.codechef.com/problems/ATMQ","time":{"view_start_date":1631727002,"submit_start_date":1631727002,"visible_start_date":1631727002,"end_date":1735669800},"is_direct_submittable":false,"problemDiscussURL":"https://discuss.codechef.com/search?q=ATMQ","is_proctored":false,"visitedContests":{},"layout":"problem"}---There are $N$ people waiting in a queue at ATM. The $i^{th}$ person in the queue has a power level equal to $A_i$ ($1 \leq A_i \leq N$). The following process happens every second till the queue is not empty.- The person in front of the queue uses the ATM and then leaves the queue.- After the first step, if the queue is empty, the process stops. Otherwise, for each person from left to right (except for the first person in the queue), if the person has a $\textbf{strictly greater}$ power level than the person in front of him, he will overtake the person in front, i.e. their positions get swapped. Note that the overtaking happens one after the other from left to right, i.e. state of the queue changes after every overtake.For each person, find the time at which they will use the ATM.$\textbf{Note}:$ Please refer to the explanation section for a simulation of one such scenario.<aside style='background: #f8f8f8;padding: 10px 15px;'><div>All submissions for this problem are available.</div></aside>