prithivMLmods/Coder-Stat

1<h1>Bozosort</h1>2    　3<p>4  Bozosort, as well as Bogosort, is a very inefficient sort algorithm. It is a random number-based algorithm that sorts sequence elements following the steps as below:5</p>6 7<ol>8<li> Randomly select two elements and swap them.</li>9<li> Verify if all the elements are sorted in increasing order.</li>10<li> Finish if sorted, else return to 1.</li>11 12</ol>13 14<p>15  To analyze Bozosort, you have decided to simulate the process using several predetermined pairs of elements.16</p>17 18<p>19  You are given several commands to swap two elements. Make a program to evaluate how many times you have to run the command before the sequence is aligned in increasing order.20</p>21 22 23<h2>Input</h2>24<p>25The input is given in the following format.26</p>27<pre>28$N$29$a_1$ $a_2$ ... $a_N$30$Q$31$x_1$ $y_1$32$x_2$ $y_2$33$...$34$x_Q$ $y_Q$35</pre>36 37<p>38The first line provides the number of sequence elements $N$ ($2 \leq N \leq 300,000$). The second line provides an array of integers $a_i$ ($1 \leq a_i \leq 10^9$) that constitutes the sequence. Each of the subsequent $Q$ lines provides a pair of integers $x_i,y_i$ ($1 \leq x_i,y_i \leq N$) that represent the $i$-th command, which swaps the two elements indicated by $x_i$ and $y_i$ ($x_i \ne y_i$).39</p>40 41<h2>Output</h2>42 43<p>44  If neat alignment in increasing order is realized the first time after execution of multiple commands, output at what time it was. Output <span>0</span> if the initial sequence is aligned in increasing order, and <span>-1</span> if exhaustive execution still failed to attain the goal.45</p>46 47<h2>Sample Input 1</h2>48<pre>496509 7 5 6 3 1513521 6532 5543 455</pre>56 57<h2>Sample Output 1</h2>58<pre>59260</pre>61 62<h2>Sample Input 2</h2>63<pre>644654 3 2 1662671 2683 469</pre>70 71<h2>Sample Output 2</h2>72<pre>73-174</pre>75 76<h2>Sample Input 3</h2>77<pre>785791 1 1 2 2801811 282</pre>83 84<h2>Sample Input 3</h2>85<pre>86087</pre>88