/* * __----~~~~~~~~~~~------___ * . . ~~//====...... __--~ ~~ * -. \_|// |||\\ ~~~~~~::::... /~ * ___-==_ _-~o~ \/ ||| \\ _/~~- * __---~~~.==~||\=_ -_--~/_-~|- |\\ \\ _/~ * _-~~ .=~ | \\-_ '-~7 /- / || \ / * .~ .~ | \\ -_ / /- / || \ / * / ____ / | \\ ~-_/ /|- _/ .|| \ / * |~~ ~~|--~~~~--_ \ ~==-/ | \~--===~~ .\ * ' ~-| /| |-~\~~ __--~~ * |-~~-_/ | | ~\_ _-~ /\ * / \ \__ \/~ \__ * _--~ _/ | .-~~____--~-/ ~~==. * ((->/~ '.|||' -_| ~~-/ , . _|| * -_ ~\ ~~---l__i__i__i--~~_/ * _-~-__ ~) \--______________--~~ * //.-~~~-~_--~- |-------~~~~~~~~ * //.-~~~--\ * ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ * * \|/ */ #define itn int #define florr floor #include<algorithm> #include<cmath> #include<stdio.h> #include<string.h> #include<iomanip> #include<iostream> #include<map> #include<queue> #include<string> #include<vector> #include<utility> #include<stack> #include<stdlib.h> #include<time.h> #include<locale> #include<sstream> #include<bitset> #include<limits.h> #include<set> #include<tr1/unordered_map> #include<ext/pb_ds/assoc_container.hpp> using namespace std; using namespace __gnu_pbds; using std::tr1::unordered_map; #define ll long long const int N=1e5+10,INF=0x3f3f3f3f; inline int read(char ch=getchar(),int n=0,int m=1) { while(ch<'0' or ch>'9') { if(ch=='-')m=-1; ch=getchar(); } while(ch>='0' and ch<='9')n=(n<<3)+(n<<1)+ch-'0',ch=getchar(); return n*m; } ostream& operator <<(ostream& o,__uint128_t &a) { __uint128_t x=a; stack<int>s; while(x)s.push(x%10),x/=10; while(!s.empty())o<<s.top(),s.pop(); return o; } int t=read(); signed main() { for(int i=1;i<=t;i++) { int n=read(),a[N],ans=-INF,b[N]; for(int j=1;j<=n;j++)a[j]=read(); for(int j=1;j<n;j++) { itn l=0,r=ans+1; while(r-l>1) { int mid=l+(r-l>>1); if(b[mid]-mid<=a[j]-j)l=mid; else r=mid; } ans=max(ans,l+1),b[l+1]=a[j]; } cout<<"Case #"<<i<<":\n"<<n-ans<<"\n"; } return 0; }