LightOJ 1166 - Old Sorting

//I am struggling
//Just Not Good at it

#include<bits/stdc++.h>

using namespace std;

#define fast ios_base::sync_with_stdio(false)
#define bfast cin.tie(0)
#define outs(x) cout << x << " "
#define outn(x) cout << x << "\n"
#define sf scanf
#define pf printf
#define nl puts("")
#define psb push_back

typedef long long LL;
typedef vector<int>vii;
typedef vector<LL>vll;
typedef map<int, int>mpii;

const int mod = 1000007;
const int high = 105;

int ar[high] , dp[high][high] , br[high];

//int rec(int i, int j)
//{
//    if(i >= j) return 0;
//
//    if(dp[i][j] >= 0) return dp[i][j];
//
//    if(ar[i] == ar[j]) dp[i][j] = rec(i+1, j-1);
//    else return dp[i][j] = 1+min(rec(i+1, j) , rec(i, j-1));
//    return dp[i][j];
//}

int main()
{
    fast;
    mpii pre, pres;
    int t , tc=0 , n , i, preindex , presindex;
    cin >> t;
    while(t--)
    {
        pre.clear();
        pres.clear();

        cin >> n;

        for(i=0; i<n; i++)
        {
            cin >> ar[i];
            pre[ar[i]] = i;
            br[i] = ar[i];
        }

        //int ans = rec(0, n-1);

        sort(br, br+n);
        //for(i=0; i<n; i++) cout << pre[ar[i]] << "; ";

        for(i=0; i<n; i++)
        {
            pres[br[i]] = i;
        }

        int cnt=0;

        for(i=0; i<n; i++)
        {
            preindex = pre[br[i]];
            presindex = pres[br[i]];


            if(ar[preindex] < ar[presindex])
            {
                //cout << ar[preindex] << " " << ar[i] << "\n";
                cnt++;
                //pre[ar[presindex]] = preindex;
                //pre[ar[preindex]] = presindex;
                swap(pre[ar[presindex]] , pre[ar[preindex]]);
                swap(ar[preindex] , ar[presindex]);
//                int tmp = ar[i];
//                ar[i] = ar[preindex];
//                ar[preindex] = tmp;
            }
        }

        cout << "Case " << ++tc << ": " << cnt << "\n";
    }

    return 0;
}