gistfile1.pyw

#!/usr/bin/env python
#-*- coding:utf-8 -*-

import sys
rdl = sys.stdin.readline

def check_sublist(current, desired, missing, to_catch):
    """Returns True if elements of desired list are in current list in the same 
        order even if there are other elements in the between"""
    it = iter(desired)
    next = it.next()
    start_pos = current.index(next)
    missing -= start_pos
    try:
        for e in current[start_pos:]:
            if missing < to_catch:
                return False
            if e == next:
                next = it.next()
                to_catch -= 1
            missing -= 1
    except StopIteration:
            return True    
        
    return False


def gen_sublists(lst, length, starting_with):
    """Yields every lst's subsequence with specified length"""
    #start = 0
    start = lst.index(starting_with)
    for i in xrange(start, len(lst)-length+1):
        yield lst[i:i+length]
        
def get_minimum_moves(l):
    """returns the minimum moves to sort l
        using worst-case first strategy"""
    ideal = sorted(l)
    k = len(ideal)
    largest = 1
    starting_with = ideal[0]
    for n in xrange(2, k+1):
        next_flag = False
        for subl in gen_sublists(ideal, n, starting_with):
            if check_sublist(l, subl, k, n):
                starting_with = subl[0]
                largest += 1
                next_flag = True
                break
        if not next_flag:
             return k-largest        


def process(case):
    input_list = [int(i) for i in rdl().split()]
    return get_minimum_moves(input_list)

cases = int(rdl())
for case in xrange(1, cases+1):
    length = int(rdl())
    p = process(case)
    print "Case #%d:"%case, p