#include <iostream>
#include <vector>
#include <map>
#include <climits>
#include <algorithm>
using namespace std;
vector<int> v, state;
int n;
map<tuple<int, int, vector<int>>, int> dp;//dp[idx][ignore(t/f)][state]
int dfs(int idx, int prev) {//prev = 0 => false, prev = 1 => true (previous skipped)
if (idx == n) return state.size();
auto key = make_tuple(idx, prev, state);
if (dp.find(key) != dp.end()) return dp[key];
//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));
// 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.pop_back();
} else {
int old = *it;
*it = v[idx];
cnt = min(cnt, dfs(idx+1, 0));
*it = old;
}
return dp[key] = cnt;
}
int main() {
cin >> n;
v.resize(n);
for (int i = 0; i < n; i++) cin >> v[i];
cout << dfs(0, 0) << endl;
}
