[USACO] 2-1-3 Sorting a Three-Valued Sequence

/*

ID: 551100k1

LANG: C++

TASK: sort3

*/

#include<stdio.h>

#include<algorithm>

using namespace std;

int a[1005],b[1005];

int s[5][5]={0};

int main(){

    freopen("sort3.in","r",stdin);

    freopen("sort3.out","w",stdout);

    int n,i,add=0,r;

    scanf("%d",&n);

    for(i=0;i<n;i++){

        scanf("%d",&a[i]);

        b[i]=a[i];

    }

    sort(b,b+n);

    for(i=0;i<n;i++)

        if(a[i]!=b[i])

            s[a[i]][b[i]]++;

    for(i=0;i<3;i++){

        r=min(s[i%3+1][(i+1)%3+1],s[(i+1)%3+1][i%3+1]);

        add+=r;

        s[i%3+1][(i+1)%3+1]-=r,s[(i+1)%3+1][i%3+1]-=r;

    }

    add+=s[1][2]*2+s[2][1]*2;

    printf("%d\n",add);

}