#include <algorithm>
#include <iostream>
#include <vector>
#include <bitset>

using namespace std;

namespace Bitmask
{
    // SHL -> (V << X) = ((V⋅2ˣ) mod (2ᵈ))
    // SHL -> (0 << X) = 0
    // SHL -> (1 << X) = ((2ˣ) mod (2ᵈ))
    //                             ^^^^
    //                             gioi han kieu du lieu
    //
    auto BinaryShiftLeft() -> void
    {
        // 10 = 8 + 2
        // 10 = 1 + 0 + 1 + 0 = 0b1010
        //      8   4   2   1  
        //    = (1 << 3) + (1 << 1) 
        //
        // (10 << 0): 0b00001010
        // (10 << 1): 0b00010100
        // (10 << 2): 0b00101000
        // (10 << 3): 0b01010000 
        // (10 << 4): 0b10100000 <-------- (-128+2⁵)
        // (10 << 5): 0b01000000 <---- 
        
        // SIGNED INT 
        //            0b10100000 <-------- (-128+32)
        //            0b10010000 <-------- (-128+16)
        //            0b10001000 <-------- (-128+8)
        //            0b10000100 <-------- (-128+4)
        //            0b10000010 <-------- (-128+2)
        //            0b10000001 <-------- (-128+1)
        //            0b10000000 <-------- (-128)
        {
            int8_t x = 10;
            for (int k = 0; k <= 7; ++k) {
                cout << int(int8_t(x << k)) << " " << bitset<8>(x << k) << endl;
            }
        }
        
        // UNSIGNED INT
        {
            uint8_t x = 10;
            for (int k = 0; k <= 7; ++k) {
                cout << int(uint8_t(x << k)) << " " << bitset<8>(x << k) << endl;
            }
        }
    }
    
    // SHR -> (V >> X) = Floor(V÷2ˣ)            (unsigned)
    auto BinaryShiftRight() -> void 
    {
        // 10 = 8 + 2
        // 10 = 1 + 0 + 1 + 0 = 0b1010
        //      8   4   2   1  
        //    = (1 << 3) + (1 << 1) 
        //
        // (10 >> 0): 0b00001010        10
        // (10 >> 1): 0b00000101         5
        // (10 >> 2): 0b00000010         2
        // (10 >> 3): 0b00000001         1
        // (10 >> 4): 0b00000000         0
        
        // UNSIGNED INT
        {
            uint8_t x = 10;
            for (int k = 0; k <= 7; ++k) {
                cout << int(uint8_t(x >> k)) << " " << bitset<8>(x >> k) << endl;
            }
        }
    }
    
    auto BinaryAnd() -> void 
    {
        uint8_t x = 27, y = 72, z = (x & y); // AND
        cout << bitset<8>(x) << " " << int(x) << endl;
        cout << bitset<8>(y) << " " << int(y) << endl;
        cout << bitset<8>(z) << " " << int(z) << endl;
        
        // X Y -> Z | X Y    Z
        // 0 0    0 | F F -> F 
        // 0 1    0 | F T -> F 
        // 1 0    0 | T F -> F 
        // 1 1    1 | T T -> T 
    }
    
    auto BinaryOr() -> void 
    {
        uint8_t x = 27, y = 72, z = (x | y); // OR
        cout << bitset<8>(x) << " " << int(x) << endl;
        cout << bitset<8>(y) << " " << int(y) << endl;
        cout << bitset<8>(z) << " " << int(z) << endl;
        
        // X Y -> Z | X Y    Z
        // 0 0    0 | F F -> F 
        // 0 1    1 | F T -> T 
        // 1 0    1 | T F -> T 
        // 1 1    1 | T T -> T 
    }
    
    auto BinaryXor() -> void 
    {
        uint8_t x = 27, y = 72, z = (x ^ y); // XOR
        cout << bitset<8>(x) << " " << int(x) << endl;
        cout << bitset<8>(y) << " " << int(y) << endl;
        cout << bitset<8>(z) << " " << int(z) << endl;
        
        // X Y -> Z | X Y    Z
        // 0 0    0 | F F -> F 
        // 0 1    1 | F T -> T 
        // 1 0    1 | T F -> T 
        // 1 1    0 | T T -> F 
    }
    
    auto BinaryAndOrXor() -> void 
    {
        uint8_t x = 27, y = 72;
        cout << bitset<8>(x) << " " << int(x) << endl;
        cout << bitset<8>(y) << " " << int(y) << endl;
        cout << bitset<8>(x & y) << " " << int(x & y) << " [AND] " << endl;
        cout << bitset<8>(x | y) << " " << int(x | y) << " [OR] " << endl;
        cout << bitset<8>(x ^ y) << " " << int(x ^ y) << " [XOR] " << endl;
    }
    
    auto GenerateBitmask(int n) -> void 
    {
        // 000..00 = 0 
        // 000..01 
        // 000..10 
        // 000..11 
        // .......
        // 111..00 
        // 111..01 
        // 111..10 
        // 111..11 = 2ⁿ-1
        
        // (MASK & (1 << BIT))
        // ????????????*???
        // 0000000000001000 (AND 2ˣ)
        // 000000000000_000
        // _ = 0 -> * = 0 
        // _ = 1 -> * = 1
        
        // ((MASK >> BIT) & 1)
        // 000????????????*
        // 0000000000000001 (AND 1)
        // 000000000000000_
        
        // _ = 0 -> * = 0 
        // _ = 1 -> * = 1
        
        for (int mask = 0; mask < (1 << n); ++mask) {
            for (int bit = 0; bit < n; ++bit) {
                cout << (mask >> bit & 1);
            }
            cout << endl;
        }
    }
    
    auto Main() -> int 
    {
        int n;
        cin >> n;
        
        // BinaryShiftLeft();
        // BinaryShiftRight();
        // BinaryAnd(); // (tat ca bit la 1) -> (ra 1)
        // BinaryOr();  // (bat ki bit la 1) -> (ra 1)
        // BinaryXor(); // (2 bit khac nhau) -> (ra 1)
        // BinaryAndOrXor();
        
        for (int n = 0; n <= 8; ++n) {
            GenerateBitmask(n);
        }
        
        return 0;
    }
}

namespace LIS
{
    int n;
    vector<int> a;
    
    auto Input() -> void
    {
        cin >> n;
        a.resize(n);
        for (int &x : a) {
            cin >> x;
        }
    }
    
    // Cho n và mảng số nguyên A[1..n], tìm độ dài dãy con tăng dài nhất của A
    namespace Problem1
    {
        auto Brute() -> int
        {
            int res = 0;
            for (int mask = 0; mask < (1 << n); ++mask) {
                
                cerr << bitset<9>(mask) << endl;
                vector<int> subsequence;
                for (int bit = 0; bit < n; ++bit) {
                    if (mask >> bit & 1) {
                        subsequence.push_back(a[bit]);
                    }
                }
                
                bool ok = true;
                for (int i = 0; i + 1 < subsequence.size(); ++i) {
                    if (subsequence[i] >= subsequence[i + 1]) {
                        ok = false;
                    }
                }
                
                if (ok) {
                    res = max(res, (int)subsequence.size());
                }
            }
            return res;
        }
        
        auto BruteFaster() -> int
        {
            int res = 0;
            for (int mask = 0; mask < (1 << n); ++mask) {
                
                cerr << bitset<9>(mask) << endl;
                vector<int> subsequence;
                for (int bit = 0; bit < n; ++bit) {
                    if (mask >> bit & 1) {
                        subsequence.push_back(a[bit]);
                    }
                }
                
                bool ok = subsequence.size() > res;
                for (int i = 0; ok && (i + 1 < subsequence.size()); ++i) {
                    if (subsequence[i] >= subsequence[i + 1]) {
                        ok = false;
                    }
                }
                
                if (ok) {
                    res = subsequence.size();
                }
            }
            return res;
        }
        
        auto BruteFasterer() -> int
        {
            int res = 0;
            for (int k = n; k >= 1; --k) {
                vector<int> bits(n, false);
                fill(bits.begin(), bits.begin() + k, true);
                
                do {
                	int last = -1;
                	bool ok = true;
                	for (int i = 0; i < n; ++i) {
                		if (!bits[i]) {
                			continue;
                		}
                		
                		if (last != -1 && a[last] > a[i]) {
                			ok = false;
                			break;
                		}
                		
                		last = i;
                	}
                	
                	if (ok) {
                		return k;
                	}
                }
                while (prev_permutation(bits.begin(), bits.end()));
            }
            return res;
        }
        
        auto Recursive(int i = 0)
        {
        	if (i >= n) {
        		return 0;
        	}
        	
        	int res = 1; // { a[i] }
        	for (int j = i + 1; j < n; ++j) {
        		if (a[i] < a[j]) {
        			res = max(res, Recursive(j) + 1); // { ... } U { a[i] }
        											  // ^^^^^^^
        		}
        	}
        	return res;
        }
        
        vector<int> dp;
        auto RecursiveDP(int i = 0)
        {
        	if (i >= n) {
        		return 0;
        	}
        	
        	int &res = dp[i];
        	if (res != 0) {
        		return res;
        	}
        	
        	res = 1; // { a[i] }
        	for (int j = i + 1; j < n; ++j) {
        		if (a[i] < a[j]) {
        			res = max(res, Recursive(j) + 1); // { ... } U { a[i] }
        											  // ^^^^^^^
        		}
        	}
        	return res;
        }
        
        auto RecursiveDP_(int i = 0)
        {
        	dp.assign(n, 0);
        	return RecursiveDP();
        }
        
        auto IterativeDP()
        {
        	// dp[i] = day tang dai nhat xet toi [i] -> ket thuc tai a[i]
        	// xet dp[j] tu dp[0..i-1], neu nhu a[j] < a[i], dp[j] + 1
        	//									^^^^^^^^^^   		 ^^^
        	//												 	 { a[i] }
        	
        	
        	// xet tat ca nhung truong hop truoc thang a[i], kiem cai thang a[j] < a[i]
        	// minh biet day tot nhat xet toi a[j] roi, thi minh chi can them a[i] vao cuoi day
        	//			 ^^^^^^^^^^^^^^^^^^^^^^^^^						 ^^^^^^^^^
        	//				do dai la dp[j]								+1 vao do dai
        	
        	vector<int> dp(n, 0);
        	for (int i = n - 1; i >= 0; --i) {
        		dp[i] = 1;
        		for (int j = i + 1; j < n; ++j) {
        			if (a[j] < a[i]) {
        				dp[i] = max(dp[i], dp[j] + 1);
        			}
        		}
        	}
        	
        	return *max_element(dp.begin(), dp.end());
        }
        
        auto Solve() -> int
        {
            return Brute();
        }
    }
    
    auto Solve() -> void
    {
        cout << Problem1::Brute() << endl;
        cout << Problem1::BruteFaster() << endl;
        cout << Problem1::BruteFasterer() << endl;
        cout << Problem1::Recursive() << endl;
        cout << Problem1::RecursiveDP_() << endl;
        cout << Problem1::IterativeDP() << endl;
    }
}

int main()
{
	LIS::Input();
    LIS::Solve();
    return 0;
}