题目链接：hdu 5773 The All-purpose Zero
官方题解：0可以转化成任意整数，包括负数，显然求LIS时尽量把0都放进去必定是正确的。
因此我们可以把0拿出来，对剩下的做O(nlogn)的LIS，统计结果的时候再算上0的数量。
为了保证严格递增，我们可以将每个权值S[i]减去i前面0的个数，再做LIS，就能保证结果是严格递增的。
个人看法：对于显然把所以0放进去部分我解释一下：
- 如果0位于最长上升子序列两边，这两个零要加进去是显然的
- 如果有一个0夹于最长上升子序列之间，那么位于LIS中0左边的数应该比0右边的数小1，而因为预处理的效果，右边的数比左边的数至少大2，所以0是可以插进去的，举个例子：1 2 3 0 4 5 6->预处理后：1 2 3 0 3 4 5，最长是1 2 3 0 4（5） 5（6），括号里是原先的数，这个例子里0是替代了原序列0右边的4
- 有许多个0夹于LIS的，同理可得
/**************************************************************
Problem:hdu 5773 The All-purpose Zero
User: youmi
Language: C++
Result: Accepted
Time:171MS
Memory:3148K
****************************************************************/
//#pragma comment(linker, "/STACK:1024000000,1024000000")
//#include<bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <stack>
#include <set>
#include <sstream>
#include <cmath>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#define zeros(a) memset(a,0,sizeof(a))
#define ones(a) memset(a,-1,sizeof(a))
#define sc(a) scanf("%d",&a)
#define sc2(a,b) scanf("%d%d",&a,&b)
#define sc3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define scs(a) scanf("%s",a)
#define sclld(a) scanf("%I64d",&a)
#define pt(a) printf("%d\n",a)
#define ptlld(a) printf("%I64d\n",a)
#define rep(i,from,to) for(int i=from;i<=to;i++)
#define irep(i,to,from) for(int i=to;i>=from;i--)
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
#define lson (step<<1)
#define rson (lson+1)
#define eps 1e-6
#define oo 0x3fffffff
#define TEST cout<<"*************************"<<endl
const double pi=*atan(1.0); using namespace std;
typedef long long ll;
template <class T> inline void read(T &n)
{
char c; int flag = ;
for (c = getchar(); !(c >= '' && c <= '' || c == '-'); c = getchar()); if (c == '-') flag = -, n = ; else n = c - '';
for (c = getchar(); c >= '' && c <= ''; c = getchar()) n = n * + c - ''; n *= flag;
}
int Pow(int base, ll n, int mo)
{
if (n == ) return ;
if (n == ) return base % mo;
int tmp = Pow(base, n >> , mo);
tmp = (ll)tmp * tmp % mo;
if (n & ) tmp = (ll)tmp * base % mo;
return tmp;
}
//*************************** int n;
const int maxn=+;
int a[maxn];
int val[maxn];
int c[maxn];
int tot;
int lowbit(int x)
{
return x&(-x);
}
void update(int temp,int x)
{
while(x<=tot)
{
c[x]=Max(c[x],temp);
x+=lowbit(x);
}
}
int query(int x)
{
int res=;
while(x)
{
res=Max(c[x],res);
x-=lowbit(x);
}
return res;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
int T_T;
scanf("%d",&T_T);
for(int kase=;kase<=T_T;kase++)
{
sc(n);
zeros(c);
int cnt=;
int tt=;
int u;
rep(i,,n)
{
sc(u);
if(u==)
cnt++;
else
{
a[tt]=u-cnt;
val[tt]=a[tt];
tt++;
}
}
sort(val,val+tt);
tot=unique(val,val+tt)-val;
int ans=;
rep(i,,tt-)
{
int temp=lower_bound(val,val+tot,a[i])-val+;
int res=query(temp-)+;
ans=Max(ans,res);
update(res,temp);
}
printf("Case #%d: %d\n",kase,ans+cnt);
}
}