SSORT - Silly Sort

Your younger brother has an assignment and needs some help. His teacher gave him a sequence of numbers to be sorted in ascending order. During the sorting process, the places of two numbers can be interchanged. Each interchange has a cost, which is the sum of the two numbers involved.

You must write a program that determines the minimal cost to sort the sequence of numbers.

Input

The input file contains several test cases. Each test case consists of two lines. The first line contains a single integer n (n>1), representing the number of items to be sorted. The second line contains n different integers (each positive and less than 1000), which are the numbers to be sorted.

The input is terminated by a zero on a line by itself.

Output

For each test case, the output is a single line containing the test case number and the minimal cost of sorting the numbers in the test case.

Place a blank line after the output of each test case.

Example

Input:
3
3 2 1
4
8 1 2 4
5
1 8 9 7 6
6
8 4 5 3 2 7
0

Output:
Case 1: 4

Case 2: 17

Case 3: 41

Case 4: 34


Added by:Fudan University Problem Setters
Date:2008-01-03
Time limit:0.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: C99 ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:ACM/ICPC World Final 2002 (unofficial testdata)

hide comments
2017-11-01 07:50:38
How to get 41 for the third case?
2015-09-19 21:28:39
Struggled for almost two days then finally got the concept .Cycle and its values.Quality problem.

Last edit: 2015-09-19 21:29:21
2013-12-01 21:47:11 Martijn Muijsers
Awesome problem, compliments!
2012-12-15 05:28:30 shivendra panicker
very good problem!!
2012-08-31 16:59:31 beginner :(
Really awesome prob :)
2012-03-27 13:39:40 littlefriend
swap(1,2)-->swap(1,4)-->swap(1,8)
2012-02-29 09:58:37 Devil D
How is the answer for second case 17 ?
2011-06-22 19:20:12 Gurpreet Singh
@wael: "The second line contains n *different* integers "
2011-05-05 15:36:37 The Scenario
Is there any repeated Number in the sequence ?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.