回路配線の最大交差したくないサブセット例えば(1,2)(2,1)

/**

 *               ！  (1,2),(2,1)         1	 

 */



#include<stdio.h>



void MNS(int c[11],int n,int size[11][11]);



int main(){



	int n;

	while(scanf("%d",&n),n){

	

		int c[11]={0};

		int size[11][11]={0};

		for(int i=1;i<=n;i++)

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

		/*for(int it=1;it<=n;it++)

			printf("%d  ",c[it]);

		putchar('
');*/

		MNS(c,n,size);

		printf("%d
",size[n][n]);

		/*for(int ji=1;ji<=n;ji++){

			for(int ij=1;ij<=n;ij++)

				printf("%d  ",size[ji][ij]);

			putchar('
');

		}*/



	}



	return 0;





}



void MNS(int c[11],int n,int size[11][11]){



	for(int i=1;i<=n;i++)

		if(i<c[1])

			size[i][i]=0;

		else

			size[1][i]=1;

	for(int j=2;j<n;j++){

		for(int k=1;k<c[j];k++)

			size[j][k]=size[j-1][k];

		for(int kk=c[j];kk<=n;kk++)

			size[j][kk]=(size[j-1][kk]>size[j-1][c[j]-1]+1)?size[j-1][kk]:size[j-1][c[j]-1]+1;

	}

	size[n][n]=size[n-1][n]>size[n-1][c[n]-1]+1?size[n-1][n]:size[n-1][c[n]-1]+1;

}