#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cstdlib>
#include<queue>
#include<set>
#include<cstdio>

using namespace std;

#define ll long long
#define rep(i, n) for(int i = 0; i < n; i++)
#define P pair<int, int>

typedef vector<int> vec;
typedef vector<vec> mat;

const ll mod = 1000000007;

deque<int> col;



int main(){
    int n;
    cin >> n;
    int a[n];
    rep(i, n) cin >> a[i];
    col.push_front(a[0]);
    for (int i = 1; i < n; i++){
        int idx = lower_bound(col.begin(), col.end(), a[i]) - col.begin();
        if(idx == 0){
            col.push_front(a[i]);
        }else{
            col[idx-1] = a[i];
        }
    }
    int ans = col.size();
    cout << ans << endl;
}
#include<bits/stdc++.h>
using namespace std;

#define _GLIBCXX_DEBUG
#define all(v) (v).begin(),(v).end()

using ll=long long;
using pii=pair<int, int>;
using vi=vector<int>;
using vii=vector<vector<int>>;

const ll LINF=1LL<<60;
const int INF=1<<29;
const ll MOD=1e9+7;



int main(){
    int N; cin >> N;
    vi A(N);
    for(auto &x : A)cin >> x;

    vector<vector<ll>> dp(N+1, vector<ll>(2, 0));
    dp[0][1]=-INF;
    for(int i=0; i<N; i++){
        dp[i+1][0]=max(dp[i][0]+A[i], dp[i][1]-A[i]);
        dp[i+1][1]=max(dp[i][0]-A[i], dp[i][1]+A[i]);
    }
    cout << dp[N][0] << endl;
    return 0;
}