{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n #problem-body \u003e pre {\n display: block;\n padding: 9.5px;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n word-break: break-all;\n word-wrap: break-word;\n color: #333;\n background: rgba(255, 255, 255, 0.5);\n border: 1px solid #ccc;\n border-radius: 6px;\n }\n\u003c/style\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv id\u003d\"problem-body\"\u003e\n\t\u003cp\u003e\u003cimg src\u003d\"CDN_BASE_URL/db21c882a409439e591bbd7a52626a25?v\u003d1715351550\" alt\u003d\"main-destinations-tirupati\" width\u003d\"215\" height\u003d\"120\" style\u003d\"float:left; margin:10px;\"\u003e\u003c/p\u003e\r\n\u003cp\u003eThe \u003ca href\u003d\"//en.wikipedia.org/wiki/Tirumala_Venkateswara_Temple\" target\u003d\"_blank\"\u003eTirumala temple \u003c/a\u003e is the most visited place of worship in the world. As the number of pilgrims who visit the temple each day is very high, the head of the temple should keep monitoring the queue system. Today is another lovely day and he has started his work. There are \u003cstrong\u003eN\u003c/strong\u003e queues at the entrance of the temple and some of them are already filled with pilgrims. Each queue has a metal door at the beginning, which leads to the temple. When the door is opened, it allows only one pilgrim to get through it and it gets closed immediately after that.\u003c/p\u003e\r\n\u003cp\u003eNew pilgrims are rushing in to the queues and the head needs to monitor the current sizes of the queues and decide which doors to be opened. At any time, he wants to know how many queues currently have at least \u003cstrong\u003eX\u003c/strong\u003e pilgrims. He also decides an integer \u003cstrong\u003eY\u003c/strong\u003e and wants to open the doors of all the queues having at least \u003cstrong\u003eY\u003c/strong\u003e pilgrims at that time. You are the controller of the queue system and are following his instructions. Respond quickly and win yourself a big laddu (sweet) from him :) .\u003c/p\u003e\r\n\u003cp\u003eRead the input section for rest of the details.\u003c/p\u003e\r\n\u003ch3\u003eInput\u003c/h3\u003e\r\n\u003cp\u003eThe first line contains two integers N and Q. N - The number of queues [1 \u0026lt;\u003d N \u0026lt;\u003d 100,000], Q - The number of queries [0 \u0026lt;\u003d Q \u0026lt;\u003d 500,000]. The second line contains N integers, which are the initial sizes of the queues. ith integer (1-based) is the initial size of queue i [0 \u0026lt;\u003d initial size \u0026lt;\u003d 100,000,000]\u003c/p\u003e\r\n\u003cp\u003eEach of the next Q lines is one of the following:\u003c/p\u003e\r\n\u003cul\u003e\r\n\u003cli\u003e1 A [One pilgrim enters the queue# A (1 \u0026lt;\u003d A \u0026lt;\u003d N)]\u003c/li\u003e\r\n\u003cli\u003e2 X [Find the number of queues having at least X pilgrims currently (0 \u0026lt;\u003d X \u0026lt;\u003d 1,000,000,000)]\u003c/li\u003e\r\n\u003cli\u003e3 Y [Open the doors of all the queues having at least Y pilgrims (1 \u0026lt;\u003d Y \u0026lt;\u003d 1,000,000,000), and thus allowing only one pilgrim to enter the temple from each of them]\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\u003ch3\u003eOutput\u003c/h3\u003e\r\n\u003cp\u003eFor each query of type \"2 X\" , print the answer in a new line.\u003c/p\u003e\r\n\u003ch3\u003eExample\u003c/h3\u003e\r\n\u003cdiv\u003e\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5 6\r\n20 30 10 50 40\r\n2 31\r\n1 2\r\n2 31\r\n3 11\r\n2 20\r\n2 50\r\n\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\r\n3\r\n3\r\n0\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/div\u003e\r\n\u003cp\u003e\u003cstrong\u003eNote:\u003c/strong\u003e\u003c/p\u003e\r\n\u003cul\u003e\r\n\u003cli\u003eIdeal time limit should be 2s. It has been increased to 7s, to let Java solutions pass, as the I/O is huge. Edit: now 1s after server update.\u003cp\u003e\u003c/p\u003e\r\n\u003c/li\u003e\u003cli\u003eThere are multiple test sets, and the judge shows the \u003cstrong\u003esum\u003c/strong\u003e of the time taken over all test sets of your submission, if accepted.\u003cp\u003e\u003c/p\u003e\r\n\u003c/li\u003e\u003c/ul\u003e\r\n\n\u003c/div\u003e"}}]}