//testing Gemini code
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// Function to compare two DP states.
// Returns true if A is "better" than B.
bool compare_states(const vector<int>& A, const vector<int>& B) {
if (A.size() != B.size()) {
return A.size() < B.size(); // Shorter LDS is strictly better
}
// If lengths are equal, we compare from the end.
// Smaller ending values make it harder to extend the decreasing sequence.
for (int i = (int)A.size() - 1; i >= 0; --i) {
if (A[i] != B[i]) {
return A[i] < B[i];
}
}
return false; // Equal
}
// Function to add an element X to state D
vector<int> add_element(vector<int> D, int X) {
// We are maintaining a strictly decreasing sequence ending values.
// We want to find the first element in D that is <= X to replace it.
auto it = lower_bound(D.begin(), D.end(), X, greater<int>());
if (it == D.end()) {
D.push_back(X); // X extends the longest decreasing sequence
} else {
*it = X; // X replaces to maximize the ending value for this length
}
return D;
}
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 == 0) {
cout << 0 << "\n";
return 0;
}
if (N == 1) {
cout << 1 << "\n";
return 0;
}
vector<int> dp_prev2; // DP[i-2]
vector<int> dp_prev1 = add_element(vector<int>(), A[0]); // DP[0]
// Evaluate DP[1]
vector<int> opt1 = add_element(dp_prev1, A[1]); // Include A[0], Include A[1]
vector<int> opt2 = add_element(vector<int>(), A[1]); // Skip A[0], Include A[1]
vector<int> dp_curr = compare_states(opt1, opt2) ? opt1 : opt2;
for (int i = 2; i < N; ++i) {
dp_prev2 = dp_prev1;
dp_prev1 = dp_curr;
vector<int> from_prev1 = add_element(dp_prev1, A[i]);
vector<int> from_prev2 = add_element(dp_prev2, A[i]);
if (compare_states(from_prev1, from_prev2)) {
dp_curr = from_prev1;
} else {
dp_curr = from_prev2;
}
}
// The answer is the length of the best LDS valid subsequence ending at N-1 or N-2
int ans = dp_curr.size();
if (compare_states(dp_prev1, dp_curr)) {
ans = dp_prev1.size();
}
cout << ans << "\n";
return 0;
}
