시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
10 초 128 MB 21 14 8 61.538%

문제

1부터 n까지 정수 n개로 이루어진 길이가 n인 수열 A가 있다. 수열의 각 원소는 서로 다르다. 이때, 다음과 같은 조건을 만족하는 수열 B를 찾으려고 한다.

B[0] > B[1] < B[2] > B[3] < ...

B는 A의 부분 수열이고, 위의 조건을 만족하는 수열 중 가장 길이가 긴 수열이다. 부분 수열이란 수열에서 원소 몇 개를 삭제해서 얻을 수 있는 수열이다. 이때, 순서는 항상 유지되어야 한다.

A가 주어졌을 때, B의 길이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. T는 최대 50이다. 각 테스트 케이스는 한 줄로 이루어져 있고, 다음과 같은 형식이다.

n A[0] A[1] A[2] ... A[n-1]

n은 최대 30000이다. 

출력

각 테스트 케이스에 대해서, B의 길이를 출력한다. 

예제 입력 1

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

예제 출력 1

1
2
5
3
W3sicHJvYmxlbV9pZCI6IjQyMzciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJlNDQgXHViMmU4XHVjODcwXHVjMTMxIiwiZGVzY3JpcHRpb24iOiJcclxuPHA+XHJcblx0MVx1YmQ4MFx1ZDEzMCBuXHVhZTRjXHVjOWMwIFx1YzgxNVx1YzIxOCBuXHVhYzFjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWFlMzhcdWM3NzRcdWFjMDAgblx1Yzc3OCBcdWMyMThcdWM1ZjQgQVx1YWMwMCBcdWM3ODhcdWIyZTQuIFx1YzIxOFx1YzVmNFx1Yzc1OCBcdWFjMDEgXHVjNmQwXHVjMThjXHViMjk0IFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzRcdWIyZTQuIFx1Yzc3NFx1YjU0YywgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWM4NzBcdWFjNzRcdWM3NDQgXHViOWNjXHVjODcxXHVkNTU4XHViMjk0IFx1YzIxOFx1YzVmNCBCXHViOTdjIFx1Y2MzZVx1YzczY1x1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdEJbMF0gJmd0OyBCWzFdICZsdDsgQlsyXSAmZ3Q7IEJbM10gJmx0OyAuLi48XC9wPlxyXG5cclxuPHA+XHJcblx0Qlx1YjI5NCBBXHVjNzU4IFx1YmQ4MFx1YmQ4NCBcdWMyMThcdWM1ZjRcdWM3NzRcdWFjZTAsIFx1YzcwNFx1Yzc1OCBcdWM4NzBcdWFjNzRcdWM3NDQgXHViOWNjXHVjODcxXHVkNTU4XHViMjk0IFx1YzIxOFx1YzVmNCBcdWM5MTEgXHVhYzAwXHVjN2E1IFx1YWUzOFx1Yzc3NFx1YWMwMCBcdWFlMzQgXHVjMjE4XHVjNWY0XHVjNzc0XHViMmU0LiBcdWJkODBcdWJkODQgXHVjMjE4XHVjNWY0XHVjNzc0XHViNzgwIFx1YzIxOFx1YzVmNFx1YzVkMFx1YzExYyBcdWM2ZDBcdWMxOGMgXHViYTg3IFx1YWMxY1x1Yjk3YyBcdWMwYWRcdWM4MWNcdWQ1NzRcdWMxMWMgXHVjNWJiXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjMjE4XHVjNWY0XHVjNzc0XHViMmU0LiBcdWM3NzRcdWI1NGMsIFx1YzIxY1x1YzExY1x1YjI5NCBcdWQ1NmRcdWMwYzEgXHVjNzIwXHVjOWMwXHViNDE4XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0QVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBCXHVjNzU4IFx1YWUzOFx1Yzc3NFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IlxyXG48cD5cclxuXHRcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IFRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBUXHViMjk0IFx1Y2Q1Y1x1YjMwMCA1MFx1Yzc3NFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgXHVkNTVjIFx1YzkwNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVhY2UwLCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1ZDYxNVx1YzJkZFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0biBBWzBdIEFbMV0gQVsyXSAuLi4gQVtuLTFdPFwvcD5cclxuXHJcbjxwPlxyXG5cdG5cdWM3NDAgXHVjZDVjXHViMzAwIDMwMDAwXHVjNzc0XHViMmU0LiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlxyXG5cdFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgQlx1Yzc1OCBcdWFlMzhcdWM3NzRcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjQyMzciLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJBbnRpbW9ub3RvbmljaXR5IiwiZGVzY3JpcHRpb24iOiI8cD5JIGhhdmUgYSBzZXF1ZW5jZSBGcmVkIG9mIGxlbmd0aCBuIGNvbXByaXNlZCBvZiBpbnRlZ2VycyBiZXR3ZWVuIDEgYW5kIG4gaW5jbHVzaXZlLiBUaGUgZWxlbWVudHMgb2YgRnJlZCBhcmUgcGFpcndpc2UgZGlzdGluY3QuIEkgd2FudCB0byBmaW5kIGEgc3Vic2VxdWVuY2UgTWFyeSBvZiBGcmVkIHRoYXQgaXMgYXMgbG9uZyBhcyBwb3NzaWJsZSBhbmQgaGFzIHRoZSBwcm9wZXJ0eSB0aGF0OjxcL3A+XHJcblxyXG48cHJlPk1hcnlbMF0gJmd0OyBNYXJ5WzFdICZsdDsgTWFyeVsyXSAmZ3Q7IE1hcnlbM10gJmx0OyAuLjxcL3ByZT5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCB3aWxsIGNvbnRhaW4gYSBzaW5nbGUgaW50ZWdlciBUIGV4cHJlc3NlZCBpbiBkZWNpbWFsIHdpdGggbm8gbGVhZGluZyB6ZXJvZXMuIFQgd2lsbCBiZSBhdCBtb3N0IDUwLiBUIHRlc3QgY2FzZXMgd2lsbCBmb2xsb3cuPFwvcD5cclxuXHJcbjxwPkVhY2ggdGVzdCBjYXNlIGlzIGNvbnRhaW5lZCBvbiBhIHNpbmdsZSBsaW5lLiBBIGxpbmUgZGVzY3JpYmluZyBhIHRlc3QgY2FzZSBpcyBmb3JtYXR0ZWQgYXMgZm9sbG93czo8XC9wPlxyXG5cclxuPHByZT5uIEZyZWRbMF0gRnJlZFsxXSBGcmVkWzJdIC4uLiBGcmVkW24tMV0uPFwvcHJlPlxyXG5cclxuPHA+d2hlcmUgbiBhbmQgZWFjaCBlbGVtZW50IG9mIEZyZWQgaXMgYW4gaW50ZWdlciBleHByZXNzZWQgaW4gZGVjaW1hbCB3aXRoIG5vIGxlYWRpbmcgemVyb2VzLiBObyBsaW5lIHdpbGwgaGF2ZSBsZWFkaW5nIG9yIHRyYWlsaW5nIHdoaXRlc3BhY2UsIGFuZCB0d28gYWRqYWNlbnQgaW50ZWdlcnMgb24gdGhlIHNhbWUgbGluZSB3aWxsIGJlIHNlcGFyYXRlZCBieSBhIHNpbmdsZSBzcGFjZS4gbiB3aWxsIGJlIGF0IG1vc3QgMzAwMDAuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlLCBvdXRwdXQgYSBzaW5nbGUgaW50ZWdlciBmb2xsb3dlZCBieSBhIG5ld2xpbmUgLS0tIHRoZSBsZW5ndGggb2YgdGhlIGxvbmdlc3Qgc3Vic2VxdWVuY2UgTWFyeSBvZiBGcmVkIHdpdGggdGhlIGRlc2lyZWQgcHJvcGVydGllczxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=