//more Gemini garbage (?)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// Maximum expected LDS length based on constraints (Ai <= 21)
const int MAX_K = 25;
struct State {
int len;
int tails[MAX_K];
State() {
len = 0;
for (int i = 0; i < MAX_K; ++i) tails[i] = 0;
}
// Standard LDS update: find first tail <= x and replace it, or append.
void update(int x) {
int pos = -1;
for (int i = 0; i < len; ++i) {
if (tails[i] <= x) {
pos = i;
break;
}
}
if (pos == -1) {
tails[len++] = x;
} else {
tails[pos] = x;
}
}
};
// Merges two states to find the component-wise minimum (the "best" tails)
State merge(const State& a, const State& b) {
if (a.len < b.len) return a;
if (b.len < a.len) return b;
State res;
res.len = a.len;
for (int i = 0; i < res.len; ++i) {
res.tails[i] = min(a.tails[i], b.tails[i]);
}
return res;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N;
if (!(cin >> N)) return 0;
vector<int> A(N);
for (int i = 0; i < N; ++i) cin >> A[i];
if (N == 1) {
cout << 1 << "\n";
return 0;
}
// dp[i] stores the best state ending at index i
// To save memory, we only need the last two states
State dp_prev2;
State dp_prev1;
dp_prev1.update(A[0]);
// Handle i = 1 explicitly
State opt1 = dp_prev1; opt1.update(A[1]);
State opt2; opt2.update(A[1]);
State dp_curr = merge(opt1, opt2);
for (int i = 2; i < N; ++i) {
State from_prev1 = dp_prev1;
from_prev1.update(A[i]);
State from_prev2 = dp_prev2;
from_prev2.update(A[i]);
dp_prev2 = dp_prev1;
dp_prev1 = dp_curr;
dp_curr = merge(from_prev1, from_prev2);
}
// The answer is the minimum length among valid ending states
cout << min(dp_curr.len, dp_prev1.len) << endl;
return 0;
}
