# 11062: 【原1062】小M爱机器人队形

### 题目描述

author: drf 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1062

## Sample Input

8
186 186 150 200 160 130 197 220


## Sample Output

4


## FineArtz's solution

/* 小M爱机器人队形 */
#include <iostream>
using namespace std;

int a[1000005], n;
int ans1[1000005], ans2[1000005], t[1000005];
int len;

int bisearch(int i){
int l = 1, r = len, mid;
while (l < r){
mid = (l + r) / 2;
if (t[mid] >= a[i])
r = mid;
else
l = mid + 1;
}
return l;
}

int main(){
cin >> n;
for (int i = 1; i <= n; ++i){
cin >> a[i];
ans1[i] = 1;
ans2[i] = 1;
}
t[1] = a[1];
len = 1;
for (int i = 2; i <= n; ++i){
if (a[i] > t[len]){
t[++len] = a[i];
}
else{
int p = bisearch(i);
t[p] = a[i];
}
ans1[i] = len;
}
len = 1;
t[1] = a[n];
for (int i = n - 1; i >= 1; --i){
if (a[i] > t[len]){
t[++len] = a[i];
}
else{
int p = bisearch(i);
t[p] = a[i];
}
ans2[i] = len;
}
int ans = 0;
for (int i = 1; i <= n; ++i)
ans = max(ans, ans1[i] + ans2[i] - 1);
cout << n - ans << endl;
return 0;
}


## yyong119's solution

#include <algorithm>
#include <cstdio>
#include <cstring>

using namespace std;

const int up = 1000001;
int a1[up], a2[up], f1[up], f2[up], g[up];

int main()
{
int n, k, maxn = 0;
scanf("%d",&n);
for(int i = 1; i <= n; i++)
{
scanf("%d", &a1[i]);
a2[n - i + 1] = a1[i];
}
memset(g, 0x7f, sizeof(g));
for(int i = 1; i <= n; i++)
{
k = lower_bound(g + 1, g + n + 1, a1[i]) - g;
f1[i] = k;
g[k] = a1[i];
}
memset(g, 0x7f, sizeof(g));
for(int i = 1; i <= n; i++)
{
k = lower_bound(g + 1, g + n + 1, a2[i]) - g;
f2[n - i + 1] = k;
g[k] = a2[i];
}
for(int i = 1; i <= n; i++) maxn = max(maxn, f1[i] + f2[i]);
printf("%d\n", n + 1 - maxn);
}