#include <iostream>
#include <vector>
#include <map>
#include <climits>
#include <algorithm>
using namespace std;
vector<int> v;
int n;
map<tuple<int, int, vector<int>>, int> dp;//dp[idx][ignore(t/f)][state]
int dfs(int idx, int prev, vector<int>& state) {//prev = 0 => false, prev = 1 => true (previous skipped)
if (idx == n) return state.size();
auto key = make_tuple(idx, prev, state);
auto temp = dp.find(key);
if (temp != dp.end()) return temp->second;
//ignore previous, state stored in decreasing order
int cnt = INT_MAX;
// case 1. ignore current idx
if (prev == 0) cnt = min(cnt, dfs(idx + 1, 1, state));
// case 2. add current
// find largest tie smaller than current
auto it = lower_bound(state.begin(), state.end(), v[idx], greater<int>());
// finds first element <= x
if (it == state.end()) {
state.push_back(v[idx]);//cant find any tie => add to end (smallest)
cnt = min(cnt, dfs(idx+1, 0, state));
state.pop_back();
} else {
int old = *it;
*it = v[idx];
cnt = min(cnt, dfs(idx+1, 0, state));
*it = old;
}
return dp[key] = cnt;
}
int main() {
cin >> n;
v.resize(n);
for (int i = 0; i < n; i++) cin >> v[i];
vector<int> state;
cout << dfs(0, 0, state) << endl;
}
