#include <bits/stdc++.h>
int arr[1000005],result[1000005] = {0},mid;
int call(int low, int high,int num) {
if( num >= result[high] ) {
return high + 1;
}
while( low < high ) {
mid = ( low + high ) /2 ;
if(num >= result[mid] && num < result[mid + 1]) {
return mid + 1;
}
else if(num >= result[mid]) {
low = mid;
}
else {
high = mid;
}
}
if(low == high) {
if(num < arr[low]) {
return low;
}
else {
return low + 1;
}
}
return 0;
}
int main() {
int n,i,j,k,index;
scanf("%i",&n);
for(i=1; i<=n; i++) {
scanf("%i",&arr[i]);
}
result[1] = arr[1];
int max = 1;
for(i=2; i<=n; i++) {
index = call(1,max,arr[i]);
result[index] = arr[i];
if(max < index) {
max = index;
}
}
printf("%i",n - max);
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CgppbnQgYXJyWzEwMDAwMDVdLHJlc3VsdFsxMDAwMDA1XSA9IHswfSxtaWQ7CgppbnQgY2FsbChpbnQgbG93LCBpbnQgaGlnaCxpbnQgbnVtKSB7CgogICAgaWYoIG51bSA+PSByZXN1bHRbaGlnaF0gKSB7CiAgICAgICAgcmV0dXJuIGhpZ2ggICsgMTsKICAgIH0KCiAgICB3aGlsZSggbG93IDwgaGlnaCApIHsKICAgICAgICBtaWQgPSAoIGxvdyArIGhpZ2ggKSAvMiA7CgogICAgICAgIGlmKG51bSA+PSByZXN1bHRbbWlkXSAmJiBudW0gPCByZXN1bHRbbWlkICsgMV0pIHsKICAgICAgICAgICAgcmV0dXJuIG1pZCArIDE7CiAgICAgICAgfQoKICAgICAgICBlbHNlIGlmKG51bSA+PSByZXN1bHRbbWlkXSkgewogICAgICAgICAgICBsb3cgPSBtaWQ7CiAgICAgICAgfQoKICAgICAgICBlbHNlIHsKICAgICAgICAgICAgaGlnaCA9IG1pZDsKICAgICAgICB9CiAgICB9CgogICAgaWYobG93ID09IGhpZ2gpIHsKICAgICAgICBpZihudW0gPCBhcnJbbG93XSkgewogICAgICAgICAgICByZXR1cm4gbG93OwogICAgICAgIH0KCiAgICAgICAgZWxzZSB7CiAgICAgICAgICAgIHJldHVybiBsb3cgKyAxOwogICAgICAgIH0KICAgIH0KICAgIHJldHVybiAwOwp9CgppbnQgbWFpbigpIHsKICAgIGludCBuLGksaixrLGluZGV4OwogICAgc2NhbmYoIiVpIiwmbik7CgogICAgZm9yKGk9MTsgICAgaTw9bjsgICBpKyspIHsKICAgICAgICBzY2FuZigiJWkiLCZhcnJbaV0pOwogICAgfQoKICAgIHJlc3VsdFsxXSA9IGFyclsxXTsKICAgIGludCBtYXggPSAxOwoKICAgIGZvcihpPTI7ICAgIGk8PW47ICAgaSsrKSB7CiAgICAgICAgaW5kZXggPSBjYWxsKDEsbWF4LGFycltpXSk7CiAgICAgICAgcmVzdWx0W2luZGV4XSA9IGFycltpXTsKICAgICAgICBpZihtYXggPCBpbmRleCkgewogICAgICAgICAgICBtYXggPSBpbmRleDsKICAgICAgICB9CiAgICB9CgogICAgcHJpbnRmKCIlaSIsbiAtIG1heCk7CgogICAgcmV0dXJuIDA7Cn0K