import java.util.ArrayList;
import java.util.Collections;
import javax.swing.JOptionPane;

/
public class TimeSort
{
  public static void main(String[] args)
  {
    int size = Integer.parseInt(JOptionPane.showInputDialog("List size?"));
	long sum = 0;
	final int LENGTH = 100;
	
	ArrayList<Integer> nums = new ArrayList<Integer>();	
		for (int a = 0; a < size; a++) {
	      nums.add(a);
	    }
	        

	for(int i = 0;i<LENGTH;i++){
	    Collections.shuffle(nums);
	    long startTime = System.currentTimeMillis();
	    Collections.sort(nums);
	    long endTime = System.currentTimeMillis();
	    sum = sum + (endTime-startTime);    
	}
	
	System.out.println(size + ":" + (sum/LENGTH));
  }
}