시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 1722 455 339 29.659%

문제

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

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

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

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

입력

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

출력

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

예제 입력 1

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

예제 출력 1

3
1
1
W3sicHJvYmxlbV9pZCI6IjM3NDUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM2MjRcdWI5ODRcdWMxMzgiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzhmY1x1YzJkZFx1ZDIyY1x1Yzc5MFx1Yjk3YyBcdWM4OGJcdWM1NDRcdWQ1NThcdWIyOTQgXHVjODE1XHVjNzc4XHVjNzc0XHViMjk0IFx1YzhmY1x1YWMwMFx1Yzc1OCBcdWM2MjRcdWI5ODRcdWMxMzhcdWI5N2MgXHVjMGI0XHVkM2I0XHViY2Y0XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjODE1XHVjNzc4XHVjNzc0XHViMjk0IG5cdWM3N2MgXHViM2Q5XHVjNTQ4IFx1YjllNFx1Yzc3YyBcdWM4ZmNcdWFjMDBcdWI5N2MgXHVjODAxXHVjNWI0XHViMTkzXHVjNTU4XHVhY2UwLCBcdWM1ZWNcdWFlMzBcdWMxMWMgXHVjNjI0XHViOTg0XHVjMTM4XHViOTdjIFx1Y2MzZVx1YzU0NFx1YmNmNFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPm5cdWM3N2MgXHViM2Q5XHVjNTQ4XHVjNzU4IFx1YzhmY1x1YWMwMFx1Yjk3YyBwPHN1Yj4xPFwvc3ViPiwgcDxzdWI+MjxcL3N1Yj4sIC4uLiwgcDxzdWI+bjxcL3N1Yj5cdWM3NzRcdWI3N2NcdWFjZTAgXHVkNTg4XHVjNzQ0IFx1YjU0YywgXHVjNjI0XHViOTg0XHVjMTM4XHViNzgwIFx1YmQ4MFx1YmQ4NFx1YzIxOFx1YzVmNCBwPHN1Yj5pPHN1Yj4xPFwvc3ViPjxcL3N1Yj4gJmx0OyBwPHN1Yj5pPHN1Yj4yPFwvc3ViPjxcL3N1Yj4gJmx0OyAuLi4gJmx0OyBwPHN1Yj5pPHN1Yj5rPFwvc3ViPjxcL3N1Yj4gKGk8c3ViPjE8XC9zdWI+ICZsdDsgaTxzdWI+MjxcL3N1Yj4gJmx0OyAuLi4gaTxzdWI+azxcL3N1Yj4pXHVjNzQ0IFx1YjlkMFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+blx1Yzc3YyBcdWIzZDlcdWM1NDggXHVjOGZjXHVhYzAwXHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YWMwMFx1YzdhNSBcdWFlMzQgXHVjNjI0XHViOTg0XHVjMTM4XHViOTdjIFx1Y2MzZVx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwIFx1YzVlY1x1YjdlY1x1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjOGZjXHVhYzAwXHViOTdjIFx1YWQwMFx1Y2MzMFx1ZDU1YyBcdWIwYTBcdWM3NTggXHVjMjE4IE4gKE4gJmxlOyAxMDAwMDApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFkMDBcdWNjMzBcdWQ1NWMgXHVjOGZjXHVhYzAwXHVhYzAwIFx1Y2NhYiBcdWIwYTBcdWJkODBcdWQxMzAgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjOGZjXHVhYzAwXHViMjk0IFx1ZDU1YyBcdWFjMWMgXHVjNzc0XHVjMGMxXHVjNzU4IFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjNzg4XHViMmU0LiBcdWM4ZmNcdWFjMDBcdWIyOTQgMzJcdWJlNDRcdWQyYjggXHVjODE1XHVjMjE4IFx1YmM5NFx1YzcwNFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMgXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNCBcdWM4ZmNcdWFjMDBcdWM3NTggXHVhYzAwXHVjN2E1IFx1YWUzNCBcdWM2MjRcdWI5ODRcdWMxMzhcdWM3NTggXHVhZTM4XHVjNzc0XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzNzQ1IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiU3RvY2sgRXhjaGFuZ2UiLCJkZXNjcmlwdGlvbiI6IjxwPlRoZSB3b3JsZCBmaW5hbmNpYWwgY3Jpc2lzIGlzIHF1aXRlIGEgc3ViamVjdC4gU29tZSBwZW9wbGUgYXJlIG1vcmUgcmVsYXhlZCB3aGlsZSBvdGhlcnMgYXJlIHF1aXRlIGFueGlvdXMuIEpvaG4gaXMgb25lIG9mIHRoZW0uIEhlIGlzIHZlcnkgY29uY2VybmVkIGFib3V0IHRoZSBldm9sdXRpb24gb2YgdGhlIHN0b2NrIGV4Y2hhbmdlLiBIZSBmb2xsb3dzIHN0b2NrIHByaWNlcyBldmVyeSBkYXkgbG9va2luZyBmb3IgcmlzaW5nIHRyZW5kcy4gR2l2ZW4gYSBzZXF1ZW5jZSBvZiBudW1iZXJzIHA8c3ViPjE8XC9zdWI+LCBwPHN1Yj4yPFwvc3ViPiwgLi4uLCBwPHN1Yj5uPFwvc3ViPiByZXByZXNlbnRpbmcgc3RvY2sgcHJpY2VzLCBhIHJpc2luZyB0cmVuZCBpcyBhIHN1YnNlcXVlbmNlIHA8c3ViPmk8c3ViPjE8XC9zdWI+PFwvc3ViPiZuYnNwOyZsdDsgcDxzdWI+aTxzdWI+MjxcL3N1Yj48XC9zdWI+Jm5ic3A7Jmx0OyAuLi4gJmx0OyBwPHN1Yj5pPHN1Yj5rPFwvc3ViPjxcL3N1Yj4sIHdpdGggaTxzdWI+MTxcL3N1Yj4gJmx0OyBpPHN1Yj4yPFwvc3ViPiAmbHQ7ICZtaWRkb3Q7ICZtaWRkb3Q7ICZtaWRkb3Q7ICZsdDsgaTxzdWI+azxcL3N1Yj4uIEpvaG4mcnNxdW87cyBwcm9ibGVtIGlzIHRvIGZpbmQgdmVyeSBxdWlja2x5IHRoZSBsb25nZXN0IHJpc2luZyB0cmVuZC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPkVhY2ggZGF0YSBzZXQgaW4gdGhlIGZpbGUgc3RhbmRzIGZvciBhIHBhcnRpY3VsYXIgc2V0IG9mIHN0b2NrIHByaWNlcy4gQSBkYXRhIHNldCBzdGFydHMgd2l0aCB0aGUgbGVuZ3RoIEwgKEwgJmxlOyAxMDAwMDApIG9mIHRoZSBzZXF1ZW5jZSBvZiBudW1iZXJzLCBmb2xsb3dlZCBieSB0aGUgbnVtYmVycyAoYSBudW1iZXIgZml0cyBhIGxvbmcgaW50ZWdlcikuIFRoZSBwcm9ncmFtIHByaW50cyB0aGUgbGVuZ3RoIG9mIHRoZSBsb25nZXN0IHJpc2luZyB0cmVuZC48XC9wPlxyXG5cclxuPHA+V2hpdGUgc3BhY2VzIGNhbiBvY2N1ciBmcmVlbHkgaW4gdGhlIGlucHV0LiBUaGUgaW5wdXQgZGF0YSBhcmUgY29ycmVjdCBhbmQgdGVybWluYXRlIHdpdGggYW4gZW5kIG9mIGZpbGUuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggc2V0IG9mIGRhdGEgdGhlIHByb2dyYW0gcHJpbnRzIHRoZSByZXN1bHQgdG8gdGhlIHN0YW5kYXJkIG91dHB1dCBmcm9tIHRoZSBiZWdpbm5pbmcgb2YgYSBsaW5lPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

ACM-ICPC > Regionals > Europe > Southeastern European Regional Contest > SEERC 2008 A번