Wa on #11

#include<bits/stdc++.h>
#define fastIO (ios::sync_with_stdio(0),cin.tie(0))
using namespace std;

const int Maxn=21;
typedef long long ll;

int n;
int a[Maxn],all[Maxn];
int dp[Maxn][Maxn],by[Maxn][Maxn];
queue<pair<int,int>> st;

int mex(int l,int r){
	bitset<Maxn> have;
	for(int i=l;i<=r;i++)
		have[a[i]]=1;
	for(int i=0;i<=18;i++)
		if(!have[i])
			return i;
}
void use(int l,int r){
	st.push({l,r});
	fill(a+l,a+r+1,mex(l,r));
}
void done(int l,int r){
	if(l==r){
		if(a[l]!=1)use(l,l);
		return;
	}
	done(l,r-1),use(l,r),use(l,r-1),done(l,r-1);
}
void dfs(int l,int r){
	if(by[l][r]==-2)return;
	if(by[l][r]==-1){
		if(mex(l,r)==r-l+1)return use(l,r),void();
		while(mex(l,r)!=1)use(l,r);
		done(l,r-1);
		use(l,r);
	}
	else dfs(l,by[l][r]),dfs(by[l][r]+1,r);
}

int main(){
	fastIO;
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i],all[i]=all[i-1]+a[i];
	
	for(int len=1;len<=n;len++){
		for(int l=1;l<=n-len+1;l++){
			int r=l+len-1;
			
			if((r-l+1)*(r-l+1)>all[r]-all[l-1])
				dp[l][r]=(r-l+1)*(r-l+1),by[l][r]=-1;
			else
				dp[l][r]=all[r]-all[l-1],by[l][r]=-2;
			
			for(int k=l;k<r;k++){
				if(dp[l][r]<=dp[l][k]+dp[k+1][r]){
					dp[l][r]=dp[l][k]+dp[k+1][r];
					by[l][r]=k;
				}
			}
		}
	}
	
	dfs(1,n);
	cout<<dp[1][n]<<' '<<st.size()<<'\n';
	while(!st.empty()){
		cout<<st.front().first<<' '<<st.front().second<<'\n';
		st.pop();
	}
	return 0;
}

Check log wrong answer The sum 1071 of the elements of the resulting array is not equal to s=1077

in

18
0 13 9 2 4 0 233 6 1 6 92 2 160 8 293 9 4 227

out

1077 63
1 2
1 1
1 3
1 2
1 2
1 1
1 4
1 3
1 2
1 1
1 3
1 2
1 2
1 1
1 5
1 4
1 2
1 1
1 3
1 2
1 2
1 1
1 4
1 3
1 2
1 1
1 3
1 2
1 2
1 1
1 6
1 5
1 2
1 1
1 3
1 2
1 2
1 1
1 4
1 3
1 2
1 1
1 3
1 2
1 2
1 1
1 5
1 4
1 2
1 1
1 3
1 2
1 2
1 1
1 4
1 3
1 2
1 1
1 3
1 2
1 2
1 1
1 6