BUBBLESORT - Bubble Sort

One of the simplest sorting algorithms, the Bubble Sort, can be expressed as (0-based array):

procedure bubbleSort( A : list of sortable items )
     n = length(A)
     repeat
          swapped = false
          for i = 1 to n-1 inclusive do
              /* if this pair is out of order */
              if A[i-1] > A[i] then
                   /* swap them and remember something changed */
                   swap( A[i-1], A[i] )
                   swapped = true
               end if
               end for
     until not swapped
end procedure

Now, given an array of N integers, you have to find out how many swap opeartions occur if the Bubble Sort algorithm is used to sort the array.

Input

Input begins with a line containing an integer T (1<=T<=100), denoting the number of test cases. Then T test cases follow. Each test case begins with a line containing an integer N (1<=N<=10000), denoting the number of integers in the array, followed by a line containing N space separated 32-bit integers.

Output

For each test case, output a single line in the format Case X: Y, where X denotes the test case number and Y denotes the number of swap operations needed modulo 10000007.

Example

Input:
1
4
3 2 1 4

Output:
Case 1: 3

Added by:imranziad
Date:2015-11-25
Time limit:0.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:AIUB CS Fest 2015 (H.M. Mehrab)

hide comments
2019-01-01 08:48:38
This is Bill,
Bill implemented the enhanced merge sort correctly,
Bill took care of the output pattern, but
Bill forgot to write Module 10000007,
Bill got many WAs,
Don't be like Bill!!
2017-11-08 06:09:55
I did not notice ‘ needed modulo 10000007’, so I got many WAs : (
2017-01-06 09:56:25
after getting 2 times tle ,get concept inversion count...finally do it...rock on!!
2016-11-26 05:48:50
take care of spaces after "Case" and after ":" . Cost me 4-5 WAs.
2016-08-20 19:52:33 Gaurav Dahima
spoilers in comments :D
2016-06-18 07:14:46
same as invcount
2016-06-15 20:35:26 Admin Deepak Baghel
just added single line in merge sort :)

Last edit: 2016-06-16 14:36:54
2016-05-25 08:33:17
absence of mod costed me 1 WA....O(nlog(n)) using modified merge sort:D
2016-03-19 21:08:47
@akshayvenkat
swap no. 0: 3 2 1 4
swap no. 1: 2 3 1 4
swap no. 2: 2 1 3 4
swap no. 3: 1 2 3 4
2016-03-04 09:13:05
How is the answer correct ?
First 3 and 2 are swapped ; swaps=1
Next 3 and 1 are swapped ; swaps=2
3 and 4 should NOT be swapped right.. Shouldn't the answer be 2?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.