시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
10 초 128 MB 19 13 7 63.636%

문제

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+XHJcblx0MVx1YmQ4MFx1ZDEzMCBuXHVhZTRjXHVjOWMwIFx1YzgxNVx1YzIxOCBuXHVhYzFjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWFlMzhcdWM3NzRcdWFjMDAgblx1Yzc3OCBcdWMyMThcdWM1ZjQgQVx1YWMwMCBcdWM3ODhcdWIyZTQuIFx1YzIxOFx1YzVmNFx1Yzc1OCBcdWFjMDEgXHVjNmQwXHVjMThjXHViMjk0IFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzRcdWIyZTQuIFx1Yzc3NCBcdWI1NGMsIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NDAgXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjI5NCBcdWMyMThcdWM1ZjQgQlx1Yjk3YyBcdWNjM2VcdWM3M2NcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRCWzBdICZndDsgQlsxXSAmbHQ7IEJbMl0gJmd0OyBCWzNdICZsdDsgLi4uPFwvcD5cclxuXHJcbjxwPlxyXG5cdEJcdWIyOTQgQVx1Yzc1OCBcdWJkODBcdWJkODQgXHVjMjE4XHVjNWY0XHVjNzc0XHVhY2UwLCBcdWM3MDRcdWM3NTggXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjI5NCBcdWMyMThcdWM1ZjQgXHVjOTExIFx1YWMwMFx1YzdhNSBcdWFlMzhcdWM3NzRcdWFjMDAgXHVhZTM0IFx1YzIxOFx1YzVmNFx1Yzc3NFx1YjJlNC4gXHViZDgwXHViZDg0IFx1YzIxOFx1YzVmNFx1Yzc3NFx1Yjc4MCBcdWMyMThcdWM1ZjRcdWM1ZDBcdWMxMWMgXHVjNmQwXHVjMThjIFx1YmE4NyBcdWFjMWNcdWI5N2MgXHVjMGFkXHVjODFjXHVkNTc0XHVjMTFjIFx1YzViYlx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzIxOFx1YzVmNFx1Yzc3NFx1YjJlNC4gXHVjNzc0IFx1YjU0YywgXHVjMjFjXHVjMTFjXHViMjk0IFx1ZDU2ZFx1YzBjMSBcdWM3MjBcdWM5YzBcdWI0MThcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRBXHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIEJcdWM3NTggXHVhZTM4XHVjNzc0XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiXHJcbjxwPlxyXG5cdFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMTggVFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFRcdWIyOTQgXHVjZDVjXHViMzAwIDUwXHVjNzc0XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWQ1NWMgXHVjOTA0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWFjZTAsIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NDAgXHVkNjE1XHVjMmRkXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRuIEFbMF0gQVsxXSBBWzJdIC4uLiBBW24tMV08XC9wPlxyXG5cclxuPHA+XHJcblx0blx1Yzc0MCBcdWNkNWNcdWIzMDAgMzAwMDBcdWM3NzRcdWIyZTQuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHJcblx0XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBCXHVjNzU4IFx1YWUzOFx1Yzc3NFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNDIzNyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkFudGltb25vdG9uaWNpdHkiLCJkZXNjcmlwdGlvbiI6IjxwPkkgaGF2ZSBhIHNlcXVlbmNlIEZyZWQgb2YgbGVuZ3RoIG4gY29tcHJpc2VkIG9mIGludGVnZXJzIGJldHdlZW4gMSBhbmQgbiBpbmNsdXNpdmUuIFRoZSBlbGVtZW50cyBvZiBGcmVkIGFyZSBwYWlyd2lzZSBkaXN0aW5jdC4gSSB3YW50IHRvIGZpbmQgYSBzdWJzZXF1ZW5jZSBNYXJ5IG9mIEZyZWQgdGhhdCBpcyBhcyBsb25nIGFzIHBvc3NpYmxlIGFuZCBoYXMgdGhlIHByb3BlcnR5IHRoYXQ6PFwvcD5cclxuXHJcbjxwcmU+TWFyeVswXSAmZ3Q7IE1hcnlbMV0gJmx0OyBNYXJ5WzJdICZndDsgTWFyeVszXSAmbHQ7IC4uPFwvcHJlPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IHdpbGwgY29udGFpbiBhIHNpbmdsZSBpbnRlZ2VyIFQgZXhwcmVzc2VkIGluIGRlY2ltYWwgd2l0aCBubyBsZWFkaW5nIHplcm9lcy4gVCB3aWxsIGJlIGF0IG1vc3QgNTAuIFQgdGVzdCBjYXNlcyB3aWxsIGZvbGxvdy48XC9wPlxyXG5cclxuPHA+RWFjaCB0ZXN0IGNhc2UgaXMgY29udGFpbmVkIG9uIGEgc2luZ2xlIGxpbmUuIEEgbGluZSBkZXNjcmliaW5nIGEgdGVzdCBjYXNlIGlzIGZvcm1hdHRlZCBhcyBmb2xsb3dzOjxcL3A+XHJcblxyXG48cHJlPm4gRnJlZFswXSBGcmVkWzFdIEZyZWRbMl0gLi4uIEZyZWRbbi0xXS48XC9wcmU+XHJcblxyXG48cD53aGVyZSBuIGFuZCBlYWNoIGVsZW1lbnQgb2YgRnJlZCBpcyBhbiBpbnRlZ2VyIGV4cHJlc3NlZCBpbiBkZWNpbWFsIHdpdGggbm8gbGVhZGluZyB6ZXJvZXMuIE5vIGxpbmUgd2lsbCBoYXZlIGxlYWRpbmcgb3IgdHJhaWxpbmcgd2hpdGVzcGFjZSwgYW5kIHR3byBhZGphY2VudCBpbnRlZ2VycyBvbiB0aGUgc2FtZSBsaW5lIHdpbGwgYmUgc2VwYXJhdGVkIGJ5IGEgc2luZ2xlIHNwYWNlLiBuIHdpbGwgYmUgYXQgbW9zdCAzMDAwMC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIG91dHB1dCBhIHNpbmdsZSBpbnRlZ2VyIGZvbGxvd2VkIGJ5IGEgbmV3bGluZSAtLS0gdGhlIGxlbmd0aCBvZiB0aGUgbG9uZ2VzdCBzdWJzZXF1ZW5jZSBNYXJ5IG9mIEZyZWQgd2l0aCB0aGUgZGVzaXJlZCBwcm9wZXJ0aWVzPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==