3

2

1 1

4

1 2 3 4

5

1 1 2 2 2

1

3

2

Hint

For the first sequence, there are two increasing subsequence: [1], [1]. So the length of the second longest increasing subsequence is also 1, same with the length of LIS.

參考链接：http://blog.csdn.net/acvay/article/details/40686171

比赛时没有读懂题目開始做结果被hack了，后来一直想nlogn的方法，无果。以后应该会想出来，以后再贴那种方法代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#include<queue>

#include<stack>

#include<vector>

#define L(x) (x<<1)

#define R(x) (x<<1|1)

#define MID(x,y) ((x+y)>>1)

#define eps 1e-8

using namespace std;

#define N 10005

int a[N],dp[N],c[N];

int n;

int main()

{

	int i,j,t;

	scanf("%d",&t);

	while(t--)

	{

		scanf("%d",&n);

		for(i=1;i<=n;i++)

			scanf("%d",&a[i]);

        int ans=0;

        for(i=1;i<=n;i++)

		{

			dp[i]=1;

			c[i]=1;

			for(j=1;j<i;j++)

			{

			   if(a[i]<=a[j]) continue;

			   if(dp[j]+1>dp[i])

			   {

			   	 dp[i]=dp[j]+1;

			   	 c[i]=c[j];

			   }

			   else

				if(dp[j]+1==dp[i])

				 c[i]=2;

			}

			if(dp[i]>ans)

				ans=dp[i];

		}

		j=0;

		for(i=1;i<=n;i++)

			if(dp[i]==ans)

		{

			j+=c[i];

			if(j>1)

				break;

		}

		if(j>1)

			printf("%d\n",ans);

		else

			printf("%d\n",ans-1);

	}

	return 0;

}