{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e\r\n\tIn this problem, you have to analyze a particular sorting algorithm. The algorithm processes a sequence of n distinct integers by swapping two adjacent sequence elements until the sequence is sorted in ascending order. For the input sequence\u003cbr /\u003e\r\n\t\u003ccenter\u003e\r\n\t\t9 1 0 5 4 ,\u003c/center\u003e\r\n\t\u003cbr /\u003e\r\n\t\u003cspan data-scayt_word\u003d\"Ultra-QuickSort\" data-scaytid\u003d\"2\"\u003eUltra-QuickSort\u003c/span\u003e produces the output\u003cbr /\u003e\r\n\t\u003ccenter\u003e\r\n\t\t0 1 4 5 9 .\u003c/center\u003e\r\n\t\u003cbr /\u003e\r\n\tYour task is to determine how many swap operations \u003cspan data-scayt_word\u003d\"Ultra-QuickSort\" data-scaytid\u003d\"3\"\u003eUltra-QuickSort\u003c/span\u003e needs to perform in order to sort a given input sequence.\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e\r\n\tThe input contains several test cases. Every test case begins with a line that contains a single integer n \u0026lt; 500,000 -- the length of the input sequence. Each of the the following n lines contains a single integer 0 \u0026le; a[i] \u0026le; 999,999,999, the \u003cspan data-scayt_word\u003d\"i-th\" data-scaytid\u003d\"1\"\u003ei-th\u003c/span\u003e input sequence element. Input is terminated by a sequence of length n \u003d 0. This sequence must not be processed.\u003c/div\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e\r\n\tFor every input sequence, your program prints a single line containing an integer number op, the minimum number of swap operations necessary to sort the given input sequence.\u003c/div\u003e"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cpre class\u003d\"sio\"\u003e\r\n5\r\n9\r\n1\r\n0\r\n5\r\n4\r\n3\r\n1\r\n2\r\n3\r\n0\r\n\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cpre class\u003d\"sio\"\u003e\r\n6\r\n0\r\n\u003c/pre\u003e"}}]}