http://poj.org/problem?id=1836
//* @author:
import java.util.Scanner;
public class Main{
private int n;
private double a[];
int b[],c[],sum[];
public Main(int n,double a[]){
this.n=n;
this.a=a;
b=new int[n+1];
c=new int[n+1];
sum=new int[n+1];
}
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
double a[]=new double[n+1];
for(int i=1;i<=n;i++){
a[i]=sc.nextDouble();//�±��1��ʼ
}
Main ma=new Main(n,a);
// ma.showB();
//ma.showC();
System.out.println(ma.doIt());
}
private void showB(){
for(int i=1;i<=n;i++){
System.out.println(b[i]+" ");
}
}
private void showC(){
for(int i=1;i<=n;i++){
System.out.println(c[i]+" ");
}
}
private void lis(){//a[]��ǰi��Ԫ���У�����������еĳ���Ϊb[i]
b[1] = 1;
for (int i=2;i<=n;i++)
{
int max = 0;
for (int j=1;j< i;j++)
{
if (a[j]< a[i] && b[j]>max)
{
max = b[j];
}
}
b[i] = max + 1;
}
// showB();
}
private void flis()//a[]�ĴӺ���ǰ��n-i+1Ԫ���У�����������еĳ���Ϊc[i]
{
c[n] = 1;
for (int i=n-1;i>=1;i--)
{
int max = 0;
for (int j=n;j>i;j--)
{
if (a[j]< a[i] && c[j]>max)
{
max = c[j];
}
}
c[i] = max + 1;
}
}
private int doIt(){
lis();
flis();
int min=n;
for(int i=1;i<=n;i++){
for (int j = i + 1; j <= n; j++) {//��ߵ������}��,���a[i]���������Լ��ȸߵ���
if (a[i] == a[j]){
if(c[i]<=c[j])
c[i]=c[j]+1;
}
}
sum[i]=n-(b[i]+c[i]-1);
if(sum[i]< min){
min=sum[i];
}
}
return min;
}
}