시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 1683 445 331 29.580%

문제

주식투자를 좋아하는 정인이는 주가의 오름세를 살펴보려고 한다.

정인이는 n일 동안 매일 주가를 적어놓았고, 여기서 오름세를 찾아보려고 한다.

n일 동안의 주가를 p1, p2, ..., pn이라고 했을 때, 오름세란 부분수열 pi1 < pi2 < ... < pik (i1 < i2 < ... ik)을 말한다.

n일 동안 주가가 주어졌을 때, 가장 긴 오름세를 찾는 프로그램을 작성하시오.

입력

입력은 여러개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 주가를 관찰한 날의 수 N (N ≤ 100000)이 주어진다. 둘째 줄에는 관찰한 주가가 첫 날부터 순서대로 주어진다. 주가는 한 개 이상의 공백으로 구분되어 있다.

출력

각 테스트 케이스에 대해서 입력으로 주어진 주가의 가장 긴 오름세의 길이를 출력한다.

예제 입력 1

6
5 2 1 4 5 3
3
1 1 1
4
4 3 2 1

예제 출력 1

3
1
1
W3sicHJvYmxlbV9pZCI6IjM3NDUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM2MjRcdWI5ODRcdWMxMzgiLCJkZXNjcmlwdGlvbiI6IjxwPlxyXG5cdFx1YzhmY1x1YzJkZFx1ZDIyY1x1Yzc5MFx1Yjk3YyBcdWM4OGJcdWM1NDRcdWQ1NThcdWIyOTQgXHVjODE1XHVjNzc4XHVjNzc0XHViMjk0IFx1YzhmY1x1YWMwMFx1Yzc1OCBcdWM2MjRcdWI5ODRcdWMxMzhcdWI5N2MgXHVjMGI0XHVkM2I0XHViY2Y0XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjODE1XHVjNzc4XHVjNzc0XHViMjk0IG5cdWM3N2MgXHViM2Q5XHVjNTQ4IFx1YjllNFx1Yzc3YyBcdWM4ZmNcdWFjMDBcdWI5N2MgXHVjODAxXHVjNWI0XHViMTkzXHVjNTU4XHVhY2UwLCBcdWM1ZWNcdWFlMzBcdWMxMWMgXHVjNjI0XHViOTg0XHVjMTM4XHViOTdjIFx1Y2MzZVx1YzU0NFx1YmNmNFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdG5cdWM3N2MgXHViM2Q5XHVjNTQ4XHVjNzU4IFx1YzhmY1x1YWMwMFx1Yjk3YyBwPHN1Yj4xPFwvc3ViPiwgcDxzdWI+MjxcL3N1Yj4sIC4uLiwgcDxzdWI+bjxcL3N1Yj5cdWM3NzRcdWI3N2NcdWFjZTAgXHVkNTg4XHVjNzQ0IFx1YjU0YywgXHVjNjI0XHViOTg0XHVjMTM4XHViNzgwIFx1YmQ4MFx1YmQ4NFx1YzIxOFx1YzVmNCBwPHN1Yj5pMTxcL3N1Yj4gJmx0OyBwPHN1Yj5pMjxcL3N1Yj4gJmx0OyAuLi4gJmx0OyBwPHN1Yj5pazxcL3N1Yj4gKGkxICZsdDsgaTIgJmx0OyAuLi4gaWspXHVjNzQ0IFx1YjlkMFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0blx1Yzc3YyBcdWIzZDlcdWM1NDggXHVjOGZjXHVhYzAwXHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YWMwMFx1YzdhNSBcdWFlMzQgXHVjNjI0XHViOTg0XHVjMTM4XHViOTdjIFx1Y2MzZVx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHJcblx0XHVjNzg1XHViODI1XHVjNzQwIFx1YzVlY1x1YjdlY1x1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjOGZjXHVhYzAwXHViOTdjIFx1YWQwMFx1Y2MzMFx1ZDU1YyBcdWIwYTBcdWM3NTggXHVjMjE4IE4gKE4gJmxlOyAxMDAwMDApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFkMDBcdWNjMzBcdWQ1NWMgXHVjOGZjXHVhYzAwXHVhYzAwIFx1Y2NhYiBcdWIwYTBcdWJkODBcdWQxMzAgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjOGZjXHVhYzAwXHViMjk0IFx1ZDU1YyBcdWFjMWMgXHVjNzc0XHVjMGMxXHVjNzU4IFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjNzg4XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlxyXG5cdFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYyBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0IFx1YzhmY1x1YWMwMFx1Yzc1OCBcdWFjMDBcdWM3YTUgXHVhZTM0IFx1YzYyNFx1Yjk4NFx1YzEzOFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjM3NDUiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJTdG9jayBFeGNoYW5nZSIsImRlc2NyaXB0aW9uIjoiPHA+VGhlIHdvcmxkIGZpbmFuY2lhbCBjcmlzaXMgaXMgcXVpdGUgYSBzdWJqZWN0LiBTb21lIHBlb3BsZSBhcmUgbW9yZSByZWxheGVkIHdoaWxlIG90aGVycyBhcmUgcXVpdGUgYW54aW91cy4gSm9obiBpcyBvbmUgb2YgdGhlbS4gSGUgaXMgdmVyeSBjb25jZXJuZWQgYWJvdXQgdGhlIGV2b2x1dGlvbiBvZiB0aGUgc3RvY2sgZXhjaGFuZ2UuIEhlIGZvbGxvd3Mgc3RvY2sgcHJpY2VzIGV2ZXJ5IGRheSBsb29raW5nIGZvciByaXNpbmcgdHJlbmRzLiBHaXZlbiBhIHNlcXVlbmNlIG9mIG51bWJlcnMgcDxzdWI+MTxcL3N1Yj4sIHA8c3ViPjI8XC9zdWI+LCAuLi4sIHA8c3ViPm48XC9zdWI+IHJlcHJlc2VudGluZyBzdG9jayBwcmljZXMsIGEgcmlzaW5nIHRyZW5kIGlzIGEgc3Vic2VxdWVuY2UgcDxzdWI+aTE8XC9zdWI+Jm5ic3A7Jmx0OyBwPHN1Yj5pMjxcL3N1Yj4mbmJzcDsmbHQ7IC4uLiAmbHQ7IHA8c3ViPmlrPFwvc3ViPiwgd2l0aCBpMSAmbHQ7IGkyICZsdDsgJm1pZGRvdDsgJm1pZGRvdDsgJm1pZGRvdDsgJmx0OyBpay4gSm9obiZyc3F1bztzIHByb2JsZW0gaXMgdG8gZmluZCB2ZXJ5IHF1aWNrbHkgdGhlIGxvbmdlc3QgcmlzaW5nIHRyZW5kLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+RWFjaCBkYXRhIHNldCBpbiB0aGUgZmlsZSBzdGFuZHMgZm9yIGEgcGFydGljdWxhciBzZXQgb2Ygc3RvY2sgcHJpY2VzLiBBIGRhdGEgc2V0IHN0YXJ0cyB3aXRoIHRoZSBsZW5ndGggTCAoTCAmbGU7IDEwMDAwMCkgb2YgdGhlIHNlcXVlbmNlIG9mIG51bWJlcnMsIGZvbGxvd2VkIGJ5IHRoZSBudW1iZXJzIChhIG51bWJlciBmaXRzIGEgbG9uZyBpbnRlZ2VyKS4gVGhlIHByb2dyYW0gcHJpbnRzIHRoZSBsZW5ndGggb2YgdGhlIGxvbmdlc3QgcmlzaW5nIHRyZW5kLjxcL3A+XHJcblxyXG48cD5XaGl0ZSBzcGFjZXMgY2FuIG9jY3VyIGZyZWVseSBpbiB0aGUgaW5wdXQuIFRoZSBpbnB1dCBkYXRhIGFyZSBjb3JyZWN0IGFuZCB0ZXJtaW5hdGUgd2l0aCBhbiBlbmQgb2YgZmlsZS4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBzZXQgb2YgZGF0YSB0aGUgcHJvZ3JhbSBwcmludHMgdGhlIHJlc3VsdCB0byB0aGUgc3RhbmRhcmQgb3V0cHV0IGZyb20gdGhlIGJlZ2lubmluZyBvZiBhIGxpbmU8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=