using System;

public class Program

{

    public static void Main()

    {

        int[] test = { 575,457,877,721,855,826,168,63,194,524,167,937,696,155,481,259,184,433,287,241,212,320,172,706,876,244,1,858,762,803,905,56,260,501,776,115,327,943,895,520,186,781,458,881,654,657,859,837,90,864,78,20,185,967,725,779,929,726,637,691,248,261,465,507,761,241,340,807,902,954,46,88,735,503,688,389,879,266,226,968,130,22,707,33,707,432,811,636,158,168,47,124,428,511,630,908,471,689,715,373,643,760,180,378,982,586,485,861,851,429,548,980,169,255,14,875,406,824,511,282,991,557,406,139,69,36,47,539,443,480,630,86,958,528,182,659,114,385,239,964,813,506,945,981,479,677,575,884,501,87,167,212,362,572,69,149,326,833,406,488,32,37,573,989,564,474,368,397,858,606,361,672,830,25,372,310,701,947,194,921,752,79,851,114,369,919,263,414,752,668,901,502,423,193,491,706,666,577,103,525,184,463,915,732,488,6,42,907,671,954,828,423,751,679,256,121,598,237,534,69,904,435,570,47,346,780,471,13,357,573,256,259,754,889,991,960,894,751,868,285,705,415,707,457,95,681,296,411,917,548,199,541,701,487,306,47,985,776,59,62,349,314,320,821,203,30,501,816,781,369,101,205,502,526,380,596,208,675,726,843,223,924,103,923,130,408,689,116,184,747,177,251,780,215,791,982,245,292,517,744,379,617,667,880,862,766,477,70,441,921,631,383,564,734,25,693,860,713,808,45,180,703,14,959,918,804,660,881,814,178,625,193,513,11,74,375,776,269,163,936,190,794,38,753,247,780,165,107,213,973,151,392,676,883,351,313,406,729,194,221,906,537,413,139,548,486,513,43,473,676,978,662,189,734,134,435,515,299,541,727,990,411,837,385,294,906,417,699,635,610,919,261,148,52,399,414,537,911,456,729,306,154,110,494,606,244,928,121,261,189,566,969,599,403,73,611,28,489,310,663,818,948,923,965,999,41,98,255,670,272,983,976,425,812,189,750,774,118,589,35,25,156,722,623,277,513,234,305,721,262,686,539,928,328,504,646,368,320,620,756,591,322,732,735,134,640,485,907,476,74,660,500,947,382,123,225,614,75,248,335,55,652,873,702,979,96,348,66,415,967,821,6,290,273,740,423,912,943,331,388,18,990,887,964,92,728,907,705,521,873,758,575,525,631,277,223,726,344,288,141,311,828,864,319,101,324,461,731,267,791,119,284,500,724,967,310,171,593,733,691,467,491,984,710,122,980,933,566,43,939,425,353,767,290,391,586,613,851,36,598,361,154,882,860,596,568,889,485,161,622,176,346,114,879,775,953,578,708,520,620,366,663,691,852,952,82,438,284,651,474,882,12,346,483,591,661,769,480,146,929,102,41,994,933,919,769,887,497,196,126,835,280,788,526,132,460,608,289,462,259,481,63,989,545,545,580,206,33,778,71,962,598,111,675,532,748,163,138,963,358,263,798,637,769,324,488,947,650,776,410,909,257,191,617,520,455,197,726,487,974,515,168,572,625,842,822,92,5,959,55,81,940,852,437,429,894,924,376,545,419,504,173,394,695,789,913,150,704,358,636,678,872,804,968,216,365,791,26,89,750,80,887,410,650,324,838,264,966,932,808,104,437,980,497,132,488,130,999,192,206,354,588,797,876,556,731,242,347,757,49,816,555,935,944,924,978,782,188,663,714,995,767,869,694,982,719,182,830,718,92,37,73,679,552,667,235,283,627,301,758,675,835,314,330,779,238,308,280,425,970,712,139,456,582,551,158,20,451,987,738,542,742,529,221,13,196,174,296,823,193,772,217,28,86,546,525,42,853,804,185,543,236,42,717,536,592,593,555,43,581,12,303,42,540,523,55,455,416,69,996,608,559,213,355,364,478,598,405,331,403,309,592,357,350,29,892,942,621,166,703,920,178,7,681,436,248,454,609,382,241,605,709,799,537,64,163,15,661,287,64,782,595,375,857,663,403,749,605,742,634,28,663,811,34,63,247,999,516,856,382,756,180,91,274,716,872,437,730,533,442,794,35,37,169,891,699,290,360,24,32,993,51,413,804,802,475,769,801,709,344,901,184,524,991,458,958,863,613,408,116,55,920,150,91,89,759,508,97,119,531,846,112,300,260,634,820,453,123,341,163,466,242,346,708,952,803,386,815,135,793,649,189,713,517,997,520,277,506,616,395,755,462,226,56,440,578,594,893,700,934,774,885,177,120,312,129,642,697,662,495,209,312,684,921,828,681,160,823,187,494,219,661,675,163,716,115,740,310,726,160 };

        Console.WriteLine(a(test));

    }

​

    static int a(int[]x){int l=x.Length,r=1,i=0,j,c;var a=new int[l];a[0]=1;while(++i<l)for(j=0;j<i;j++){c=x[j]<x[i]?a[j]+1:1;a[i]=a[i]<c?c:a[i];r=r<c?c:r;}return r;}

}