prithivMLmods/Coder-Stat

1 2 3<H1>Problem I: FIMO sequence</H1>4<p>5Your task is to simulate the sequence defined in the remaining part of the problem description.6</p>7 8<p>9This sequence is empty at first.10<i> i </i>-th element of this sequence is expressed as <i> a<sub>i</sub> </i>.11The first element of this sequence is <i> a<sub>1</sub> </i> if the sequence is not empty.12The operation is given by integer from 0 to 9.13The operation is described below.14</p>15 16<p>170:18This query is given with some integer <i>x</i>.19If this query is given, the integer x is inserted into the sequence.20If the sequence is empty, <i>a<sub>1</sub></i> = <i>x</i>.21If the sequence has <i>n</i> elements, <i>a<sub>n+1</sub></i> = <i>x</i>.22Same integer will not appear more than once as <i>x</i>.23</p>24 25<p>261:27If this query is given, one element in the sequence is deleted.28The value in the middle of the sequence is deleted.29If the sequence has <i>n</i> elements and <i> n </i> is even, <i> a<sub>n/2</sub> </i> will be deleted.30If <i> n </i> is odd, <i> a<sub>&lceil;n/2&rceil;</sub> </i> will be deleted.31This query is not given when the sequence is empty.32 33Assume that the sequence has <i> a<sub>1</sub> </i>=1,<i> a<sub>2</sub> </i>=2,<i> a<sub>3</sub> </i>=3,<i> a<sub>4</sub> </i>=4 and <i> a<sub>5</sub> </i>=5.34In this case, <i> a<sub>3</sub> </i> will be deleted.35After deletion, the sequence will be <i> a<sub>1</sub> </i>=1, <i> a<sub>2</sub> </i>=2,<i> a<sub>3</sub> </i>=4,<i> a<sub>4</sub> </i>=5.36 37Assume that the sequence has <i> a<sub>1</sub> </i>=1,<i> a<sub>2</sub> </i>=2,<i> a<sub>3</sub> </i>=3 and <i> a<sub>4</sub> </i>=4,38In this case, <i> a<sub>2</sub> </i> will be deleted.39After deletion, the sequence will be <i> a<sub>1</sub> </i>=1,<i> a<sub>2</sub> </i>=3, <i> a<sub>3</sub> </i>=4.40</p>41 42<p>432:44The first half of the sequence is defined by the index from 1 to &lceil;<i>n</i>/2&rceil; .45If this query is given, you should compute the minimum element of the first half of the sequence.46This query is not given when the sequence is empty.47</p>48 49<p>50Let me show an example.<br>51Assume that the sequence is {6,2,3,4,5,1,8}.52In this case, the minimum element of the first half of the sequence, {6,2,3,4} is 2.53</p>54 55 56<p>573:58The latter half of the sequence is elements that do not belong to the first half of the sequence.59If this query is given, you should compute the minimum element of the latter half of the sequence.60This query is not given when the sequence is empty.61</p>62 63<p>64Let me show an example.<br>65Assume that the sequence is {6,2,3,4,5,1,8}.66In this case the answer for this query is 1 from {5,1,8}.67</p>68 69<p>704:71This query is given with an integer <i>i</i>.72Assume that deletion is repeated until the sequence is empty.73Some elements in the first half of the sequence will become the answer for query 2.74You should compute the <i> i </i>-th minimum element from the answers.75This query is not given when the sequence is empty.76You can assume that <i> i </i>-th minimum element exists when this query is given.77</p>78 79<p>80Let me show an example.81</p>82<pre>83Assume that deletion will be repeated to the sequence {6,2,3,4,5,1,8}.84{6,2,3,4,5,1,8} The minimum element in the first half of the sequence is 2.85{6,2,3,5,1,8}   The minimum element in the first half of the sequence is 2.86{6,2,5,1,8}     The minimum element in the first half of the sequence is 2.87{6,2,1,8}       The minimum element in the first half of the sequence is 2.88{6,1,8}         The minimum element in the first half of the sequence is 1.89{6,8}           The minimum element in the first half of the sequence is 6.90{8}             The minimum element in the first half of the sequence is 8.91{}              The first half of the sequence is empty.92</pre>93<p>94For the initial state, {6,2,3,4} is the first half of the sequence.952 and 6 become the minimum element of the first half of the sequence.96In this example, the 1-st minimum element is 2 and the 2-nd is 6.97</p>98 99<p>1005:101This query is given with an integer <i> i </i>.102Assume that deletion is repeated until the sequence is empty.103Some elements in the latter half of the sequence will become the answer for query 3.104You should compute the <i> i </i>-th minimum element from the answers.105This query is not given when the sequence is empty.106You can assume that <i> i </i>-th minimum element exists when this query is given.107</p>108 109<p>110Let me show an example.111</p>112<pre>113Assume that deletion will be repeated to the sequence {6,2,3,4,5,1,8}.114{6,2,3,4,5,1,8} The minimum elemets in the latter half of the sequence is 1.115{6,2,3,5,1,8}   The minimum elemets in the latter half of the sequence is 1.116{6,2,5,1,8}     The minimum elemets in the latter half of the sequence is 1.117{6,2,1,8}       The minimum elemets in the latter half of the sequence is 1.118{6,1,8}         The minimum elemets in the latter half of the sequence is 8.119{6,8}           The minimum elemets in the latter half of the sequence is 8.120{8}             The latter half of the sequence is empty.121{}              The latter half of the sequence is empty.122</pre>123<p>124For the initial state, {5,1,8} is the latter half of the sequence.1251 and 8 becomes the minimum element of the latter half ot the sequence.126In this example, the 1-st minimum element is 1 and the 2-nd is 8.127</p>128 129<p>1306:131If this query is given, you should compute the maximum element of the first half of the sequence.132This query is not given when the sequence is empty.133</p>134<p>135Let me show an example.<br>136Assume that the sequence is {1,3,2,5,9,6,7}.137In this case, the maximum element of the first half of the sequence,{1,3,2,5}, is 5.138</p>139 140<p>1417:142If this query is given, you should compute the maximum element of the latter half of the sequence.143This query is not given when the sequence is empty.144</p>145 146<p>147Let me show an example.<br>148Assume that the sequence is {1,3,2,5,9,6,7}.149In this case, the maximum element of the latter half of the sequence,{9,6,7}, is 9.150</p>151 152<p>1538:154This query is given with an integer <i> i </i>.155Assume that deletion is repeated until the sequence is empty.156Some elements in the first half of the sequence will become the answer for query 6.157You should compute the <i> i </i>-th maximum element from the answers.158This query is not given when the sequence is empty.159You can assume that <i> i </i>-th maximum elements exists when this query is given.160</p>161 162<p>Let me show an example.</p>163<pre>164Assume that deletion will be repeated to the sequence {1,3,2,5,9,6,7}.165{1,3,2,5,9,6,7} The maximum element in the first half of the sequence is 5.166{1,3,2,9,6,7}   The maximum element in the first half of the sequence is 3.167{1,3,9,6,7}     The maximum element in the first half of the sequence is 9.168{1,3,6,7}       The maximum element in the first half of the sequence is 3.169{1,6,7}         The maximum element in the first half of the sequence is 6.170{1,7}           The maximum element in the first half of the sequence is 1.171{7}             The maximum element in the first half of the sequence is 7.172{}              The first half of the sequence is empty.173</pre>174<p>175For the initial state, {1,3,2,5} is the first half of the sequence.1761,3 and 5 becomes the maximum element of the first half of the sequence.177In this example, the 1-st maximum element is 5, the 2-nd is 3 and the 3-rd is 1.178</p>179 180<p>1819:182This query is given with an integer <i> i </i>.183Assume that deletion is repeated until the sequence is empty.184Some elements in the latter half of the sequence will become the answer for query 7.185You should compute the <i> i </i>-th maximum element from the answers.186This query is not given when the sequence is empty.187You can assume that <i> i </i>-th maximum elements exists when this query is given.188</p>189 190<p>Let me show an example.</p>191<pre>192Assume that deletion will be repeated to the sequence {1,3,2,5,9,6,7}.193{1,3,2,5,9,6,7} The maximum element in the latter half of the sequence is 9.194{1,3,2,9,6,7}   The maximum element in the latter half of the sequence is 9.195{1,3,9,6,7}     The maximum element in the latter half of the sequence is 7.196{1,3,6,7}       The maximum element in the latter half of the sequence is 7.197{1,6,7}         The maximum element in the latter half of the sequence is 7.198{1,7}           The maximum element in the latter half of the sequence is 7.199{7}             The latter half of the sequence is empty.200{}              The latter half of the sequence is empty.201</pre>202<p>203For the initial state, {9,6,7} is the latter half of the sequence.2047 and 9 becomes the maximum element of the latter half of the sequence.205In this example, the 1-st maximum element is 9 and the 2-nd is 7.206</p>207 208<h2>Input</h2>209<p>210Input consists of multiple test cases.211The first line is the number of queries.212Following q lines are queries.213</p>214<pre>215<i>q</i>216<i>query<sub>0</sub></i>217...218<i>query<sub>i</sub></i>219...220<i>qurey_<sub>q-1</sub></i>221</pre>222 223<p>224The sum of the number of queries in the input data is less than 200001.225If <i>query<sub>i</sub></i> = 0, 4, 5, 8, and 9 are consists of pair of integers.226Other queries are given with a single integer.227You can assume that the length of the sequence doesn't exceed 20000.228</p>229 230<h2>Output</h2>231<p>232If the query is 0, you don't output any numbers.233If the query is 1, you should output the deleted number.234For other queries, you should output the computed value.235For each case, you should output "end" (without quates) after you process all queries.236</p>237 238<h2>Sample input</h2>239<pre>24052410 12420 22430 32440 4245124662470 12480 22490 32500 42510 52521253312540 62550 22560 32570 42580 52590 12600 82614 12624 22635 12645 226522663267126822693270127122723273127422753276127722783279128022813282128322841285322860 12870 32880 22890 52900 92910 62920 72938 12948 22958 32969 12979 2298629973001301630273031304630573061307630873091310631173121313631473151316631713180319</pre>320 321<h2>Sample output</h2>322<pre>3232324end3253326end327232863291330833123321333433423351336333723381339534023411342234313448345134663478348634983508351end3525353335413559356735753589359536033619362236393647365936633677368336963707371637213737374137573767377end378</pre>379