You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
47 lines
972 B
47 lines
972 B
#include <bits/stdc++.h>
|
|
|
|
using namespace std;
|
|
const int N = 1010;
|
|
int n, a[N];
|
|
int f[N], fl, p1[N];
|
|
int g[N], gl, p2[N];
|
|
|
|
int res;
|
|
|
|
int main() {
|
|
cin >> n;
|
|
for (int i = 1; i <= n; i++) cin >> a[i];
|
|
|
|
// 正向
|
|
f[++fl] = a[1];
|
|
p1[1] = 1;
|
|
|
|
for (int i = 2; i <= n; i++)
|
|
if (a[i] > f[fl]) {
|
|
f[++fl] = a[i];
|
|
p1[i] = fl;
|
|
} else {
|
|
int t = lower_bound(f + 1, f + fl + 1, a[i]) - f;
|
|
f[t] = a[i];
|
|
p1[i] = t;
|
|
}
|
|
|
|
// 反向
|
|
g[++gl] = a[n];
|
|
p2[n] = 1;
|
|
|
|
for (int i = n - 1; i >= 1; i--)
|
|
if (a[i] > g[gl]) {
|
|
g[++gl] = a[i];
|
|
p2[i] = gl;
|
|
} else {
|
|
int t = lower_bound(g + 1, g + gl + 1, a[i]) - g;
|
|
g[t] = a[i];
|
|
p2[i] = t;
|
|
}
|
|
|
|
for (int i = 1; i <= n; i++) res = max(res, p2[i] + p1[i] - 1);
|
|
|
|
printf("%d\n", n - res);
|
|
return 0;
|
|
} |