| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 791 人关注过本帖
标题:求助 Antimonotonicity
只看楼主 加入收藏
莫北
Rank: 1
来 自:内蒙古师范大学
等 级:新手上路
帖 子:5
专家分:0
注 册:2008-3-16
收藏
 问题点数:0 回复次数:0 
求助 Antimonotonicity
Antimonotonicity

Time Limit:2000MS  Memory Limit:65536K
Total Submit:221 Accepted:21

Description

I have a sequence Fred of length n comprised of integers between 1 and n inclusive. The elements of Fred are pairwise distinct. I want to find a subsequence Mary of Fred that is as long as possible and has the property that:
Mary0 > Mary1 < Mary2 > Mary3 < ...


Input

The first line of input will contain a single integer T expressed in decimal with no leading zeroes. T will be at most 50. T test cases will follow.
Each test case is contained on a single line. A line describing a test case is formatted as follows:
n Fred0 Fred1 Fred2 ... Fredn-1.
where n and each element of Fred is an integer expressed in decimal with no leading zeroes. No line will have leading or trailing whitespace, and two adjacent integers on the same line will be separated by a single space. n will be at most 30000.


Output

For each test case, output a single integer followed by a newline --- the length of the longest subsequence Mary of Fred with the desired properties.

Sample Input


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

Sample Output


1
2
5
3
搜索更多相关主题的帖子: expressed property elements possible sequence 
2008-03-22 11:40
快速回复:求助 Antimonotonicity
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.020541 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved