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