#include<bits/stdc++.h>
#define ll long long
using namespace std;
class node
{
public :
ll pre,suff ,ans;
bool has_0;
node()
{
pre = suff = ans = has_0 = 0;
}
};
void build(node *tree,ll *a,ll tree_index,ll start,ll end)
{
if(start>end)
return;
if(start == end)
{
//a[start] == 1 ? tree[tree_index].has_0=0,pre=suff=ans=1 ? tree[tree_index].has_0=1,pre=suff=ans=0;
if(a[start] == 1)
{
tree[tree_index].has_0 = 0;
tree[tree_index].pre = 1;
tree[tree_index].suff = 1;
tree[tree_index].ans = 1;
}
else
{
tree[tree_index].has_0 = 1;
tree[tree_index].pre = 0;
tree[tree_index].suff = 0;
tree[tree_index].ans = 0;
}
//cout<<tree_index<<" "<<start<<" "<<tree[tree_index].ans<<endl;
return;
}
ll mid = start + end;
mid >>= 1;
build(tree,a,2*tree_index,start,mid);
build(tree,a,2*tree_index+1,mid+1,end);
// for parent has_0
if(tree[2*tree_index].has_0 == 1 || tree[2*tree_index + 1].has_0 == 1)
tree[tree_index].has_0 = 1;
else if(tree[2*tree_index].has_0 == 0 && tree[2*tree_index + 1].has_0 == 0)
{
// 1. Both do not contain 0
tree[tree_index].has_0 = 0;
tree[tree_index].pre = tree[tree_index].suff = tree[tree_index].ans = end-start+1;
return;
}
// 2. if left child contains 0
if(tree[2*tree_index].has_0 == 1 && tree[2*tree_index+1].has_0 == 0)
{
tree[tree_index].pre = tree[2*tree_index].pre;
tree[tree_index].suff = tree[2*tree_index].suff + end - mid;
tree[tree_index].ans = max(tree[tree_index].suff, max(tree[2*tree_index].ans , tree[2*tree_index+1].ans));
return;
}
// 3. if right child contains 0
if(tree[2*tree_index].has_0 == 1 && tree[2*tree_index+1].has_0 == 0)
{
tree[tree_index].pre = tree[2*tree_index+1].pre + mid - start + 1;
tree[tree_index].suff = tree[2*tree_index+1].suff;
tree[tree_index].ans = max(tree[tree_index].pre, max(tree[2*tree_index].ans , tree[2*tree_index+1].ans));
return;
}
// 4. if both contains 0
tree[tree_index].pre = tree[2*tree_index].pre;
tree[tree_index].suff = tree[2*tree_index+1].suff;
tree[tree_index].ans = max(tree[2*tree_index].suff+tree[2*tree_index+1].pre,max(tree[2*tree_index].ans,tree[2*tree_index+1].ans));
}
//its returning the answer but have to return a node
/*
ll query(node *tree,ll tree_index,ll start,ll end,ll query_start,ll query_end)
{
// 1. No overlap
if(start > query_end || end < query_start)
return minv;
// 2. Complete overlap
if(start >= query_start && end <= query_end)
{
return tree[tree_index].ans;
}
ll mid = start + end;
mid >>= 1;
ll leftans = query(tree,2*tree_index,start,mid, query_start,query_end);
ll rightans = query(tree,2*tree_index + 1,mid+1,end, query_start,query_end);
// merge answer :(
ll mergeans = 1; //???
//return max(merge_ans,max(leftans,rightans));
return max(mergeans, max(leftans,rightans));
}*/
node query(node *tree,ll tree_index,ll start,ll end,ll query_start,ll query_end)
{
node a,b,c;
if(query_start >= start && query_end <= end)
{
return tree[tree_index];
}
ll mid = start + end;
mid >>= 1;
b = query(tree,2*tree_index,start,mid,query_start,query_end);
c = query(tree,2*tree_index+1,mid+1,end,query_start,query_end);
// yeah i know its wrong
// but can't figure it out what to do :(
// .....
}
int main()
{
ll n,i,j,x,y,q,k,val;
cin>>n>>q>>k;
ll a[2*n] = {0};
for(i = 0;i<n;i++)
cin>>a[i],
a[n+i] = a[i];
node tree[8*n+4];
build(tree,a,1,0,2*n-1);
//for(i = 1;i<=26;i++)
//cout<<i<<"\t"<<tree[i].ans<<"\t"<<tree[i].pre<<"\t"<<tree[i].suff<<"\t"<<tree[i].has_0<<endl;
j = 0;
// just for testing purpose
/*while(1)
{
//cin>>j;
//cout<<j<<" ";
node node1 = query(tree,1,0,n-1, j,j+n-1);
cout<<j<<" "<<j+n-1<<" "<<node1.ans<<" "<<node1.pre<<" "<<node1.suff<<endl;
j++;
}*/
/*string que = "";
cin>>que;
i = 0;
j = 0;
while(i<que.length())
{
if(que[i] == '!')
{
j++;
if(j == n)
j = 0;
}
//cout<<x<<" "<<y<<"\t";
else
{
//cout<<j<<" "<<j+n-1<<"\t";
val = query(tree,1,0,2*n-1, j,j+n-1).ans;
cout<<val<<endl;
//cout<<min(k,val)<<endl;
}
i++;
}*/
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KI2RlZmluZSBsbCBsb25nIGxvbmcKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKY2xhc3Mgbm9kZQp7CglwdWJsaWMgOiAKCWxsIHByZSxzdWZmICxhbnM7Cglib29sIGhhc18wOwoJbm9kZSgpCgl7CgkJcHJlID0gc3VmZiA9IGFucyA9IGhhc18wID0gMDsKCX0KfTsKdm9pZCBidWlsZChub2RlICp0cmVlLGxsICphLGxsIHRyZWVfaW5kZXgsbGwgc3RhcnQsbGwgZW5kKQp7CglpZihzdGFydD5lbmQpCglyZXR1cm47CglpZihzdGFydCA9PSBlbmQpCgl7CgkJCgkJLy9hW3N0YXJ0XSA9PSAxID8gdHJlZVt0cmVlX2luZGV4XS5oYXNfMD0wLHByZT1zdWZmPWFucz0xID8gdHJlZVt0cmVlX2luZGV4XS5oYXNfMD0xLHByZT1zdWZmPWFucz0wOwoJCWlmKGFbc3RhcnRdID09IDEpCgkJewoJCQl0cmVlW3RyZWVfaW5kZXhdLmhhc18wID0gMDsKCQkJdHJlZVt0cmVlX2luZGV4XS5wcmUgPSAxOwoJCQl0cmVlW3RyZWVfaW5kZXhdLnN1ZmYgPSAxOwoJCQl0cmVlW3RyZWVfaW5kZXhdLmFucyA9IDE7CgkJfQoJCWVsc2UKCQl7CgkJCXRyZWVbdHJlZV9pbmRleF0uaGFzXzAgPSAxOwoJCQl0cmVlW3RyZWVfaW5kZXhdLnByZSA9IDA7CgkJCXRyZWVbdHJlZV9pbmRleF0uc3VmZiA9IDA7CgkJCXRyZWVbdHJlZV9pbmRleF0uYW5zID0gMDsKCQl9CgkJLy9jb3V0PDx0cmVlX2luZGV4PDwiICI8PHN0YXJ0PDwiICI8PHRyZWVbdHJlZV9pbmRleF0uYW5zPDxlbmRsOwoJCXJldHVybjsJCgl9CglsbCBtaWQgPSBzdGFydCArIGVuZDsKCW1pZCA+Pj0gMTsKCQoJYnVpbGQodHJlZSxhLDIqdHJlZV9pbmRleCxzdGFydCxtaWQpOwoJYnVpbGQodHJlZSxhLDIqdHJlZV9pbmRleCsxLG1pZCsxLGVuZCk7CgkKCS8vIGZvciBwYXJlbnQgaGFzXzAKCWlmKHRyZWVbMip0cmVlX2luZGV4XS5oYXNfMCA9PSAxIHx8IHRyZWVbMip0cmVlX2luZGV4ICsgMV0uaGFzXzAgPT0gMSkKCXRyZWVbdHJlZV9pbmRleF0uaGFzXzAgPSAxOwoJZWxzZSBpZih0cmVlWzIqdHJlZV9pbmRleF0uaGFzXzAgPT0gMCAmJiB0cmVlWzIqdHJlZV9pbmRleCArIDFdLmhhc18wID09IDApCgl7CgkJLy8gMS4gQm90aCBkbyBub3QgY29udGFpbiAwCgkJCgkJdHJlZVt0cmVlX2luZGV4XS5oYXNfMCA9IDA7CgkJdHJlZVt0cmVlX2luZGV4XS5wcmUgPSB0cmVlW3RyZWVfaW5kZXhdLnN1ZmYgPSB0cmVlW3RyZWVfaW5kZXhdLmFucyA9IGVuZC1zdGFydCsxOwoJCXJldHVybjsKCX0KCQoJLy8gMi4gaWYgbGVmdCBjaGlsZCBjb250YWlucyAwCglpZih0cmVlWzIqdHJlZV9pbmRleF0uaGFzXzAgPT0gMSAmJiB0cmVlWzIqdHJlZV9pbmRleCsxXS5oYXNfMCA9PSAwKQoJewoJCXRyZWVbdHJlZV9pbmRleF0ucHJlID0gdHJlZVsyKnRyZWVfaW5kZXhdLnByZTsKCQl0cmVlW3RyZWVfaW5kZXhdLnN1ZmYgPSB0cmVlWzIqdHJlZV9pbmRleF0uc3VmZiArIGVuZCAtIG1pZDsKCQl0cmVlW3RyZWVfaW5kZXhdLmFucyA9IG1heCh0cmVlW3RyZWVfaW5kZXhdLnN1ZmYsIG1heCh0cmVlWzIqdHJlZV9pbmRleF0uYW5zICwgdHJlZVsyKnRyZWVfaW5kZXgrMV0uYW5zKSk7CQoJCXJldHVybjsJCgl9CgkKCS8vIDMuIGlmIHJpZ2h0IGNoaWxkIGNvbnRhaW5zIDAKCWlmKHRyZWVbMip0cmVlX2luZGV4XS5oYXNfMCA9PSAxICYmIHRyZWVbMip0cmVlX2luZGV4KzFdLmhhc18wID09IDApCgl7CgkJdHJlZVt0cmVlX2luZGV4XS5wcmUgPSB0cmVlWzIqdHJlZV9pbmRleCsxXS5wcmUgKyBtaWQgLSBzdGFydCArIDE7CgkJdHJlZVt0cmVlX2luZGV4XS5zdWZmID0gdHJlZVsyKnRyZWVfaW5kZXgrMV0uc3VmZjsKCQl0cmVlW3RyZWVfaW5kZXhdLmFucyA9IG1heCh0cmVlW3RyZWVfaW5kZXhdLnByZSwgbWF4KHRyZWVbMip0cmVlX2luZGV4XS5hbnMgLCB0cmVlWzIqdHJlZV9pbmRleCsxXS5hbnMpKTsJCgkJcmV0dXJuOwkKCX0KCQoJLy8gNC4gaWYgYm90aCBjb250YWlucyAwCgl0cmVlW3RyZWVfaW5kZXhdLnByZSA9IHRyZWVbMip0cmVlX2luZGV4XS5wcmU7Cgl0cmVlW3RyZWVfaW5kZXhdLnN1ZmYgPSB0cmVlWzIqdHJlZV9pbmRleCsxXS5zdWZmOwoJdHJlZVt0cmVlX2luZGV4XS5hbnMgPSBtYXgodHJlZVsyKnRyZWVfaW5kZXhdLnN1ZmYrdHJlZVsyKnRyZWVfaW5kZXgrMV0ucHJlLG1heCh0cmVlWzIqdHJlZV9pbmRleF0uYW5zLHRyZWVbMip0cmVlX2luZGV4KzFdLmFucykpOwoJCn0KLy9pdHMgcmV0dXJuaW5nIHRoZSBhbnN3ZXIgYnV0IGhhdmUgdG8gcmV0dXJuIGEgbm9kZQovKgpsbCBxdWVyeShub2RlICp0cmVlLGxsIHRyZWVfaW5kZXgsbGwgc3RhcnQsbGwgZW5kLGxsIHF1ZXJ5X3N0YXJ0LGxsIHF1ZXJ5X2VuZCkKewoJLy8gMS4gTm8gb3ZlcmxhcAoJaWYoc3RhcnQgPiBxdWVyeV9lbmQgfHwgZW5kIDwgcXVlcnlfc3RhcnQpCglyZXR1cm4gbWludjsKCQoJLy8gMi4gQ29tcGxldGUgb3ZlcmxhcAoJaWYoc3RhcnQgPj0gcXVlcnlfc3RhcnQgJiYgZW5kIDw9IHF1ZXJ5X2VuZCkKCXsKCQlyZXR1cm4gdHJlZVt0cmVlX2luZGV4XS5hbnM7Cgl9CglsbCBtaWQgPSBzdGFydCArIGVuZDsKCW1pZCA+Pj0gMTsKCWxsIGxlZnRhbnMgPSBxdWVyeSh0cmVlLDIqdHJlZV9pbmRleCxzdGFydCxtaWQsIHF1ZXJ5X3N0YXJ0LHF1ZXJ5X2VuZCk7CglsbCByaWdodGFucyA9IHF1ZXJ5KHRyZWUsMip0cmVlX2luZGV4ICsgMSxtaWQrMSxlbmQsIHF1ZXJ5X3N0YXJ0LHF1ZXJ5X2VuZCk7CgkKCQoJLy8gbWVyZ2UgYW5zd2VyIDooCglsbCBtZXJnZWFucyA9IDE7ICAgIC8vPz8/ICAKCS8vcmV0dXJuIG1heChtZXJnZV9hbnMsbWF4KGxlZnRhbnMscmlnaHRhbnMpKTsKCXJldHVybiBtYXgobWVyZ2VhbnMsIG1heChsZWZ0YW5zLHJpZ2h0YW5zKSk7CgkKfSovCm5vZGUgcXVlcnkobm9kZSAqdHJlZSxsbCB0cmVlX2luZGV4LGxsIHN0YXJ0LGxsIGVuZCxsbCBxdWVyeV9zdGFydCxsbCBxdWVyeV9lbmQpCnsKCW5vZGUgYSxiLGM7CgkKCWlmKHF1ZXJ5X3N0YXJ0ID49IHN0YXJ0ICYmIHF1ZXJ5X2VuZCA8PSBlbmQpCgl7CgkJcmV0dXJuIHRyZWVbdHJlZV9pbmRleF07CgkJCgl9CglsbCBtaWQgPSBzdGFydCArIGVuZDsKCW1pZCA+Pj0gMTsKCQoJCgliID0gcXVlcnkodHJlZSwyKnRyZWVfaW5kZXgsc3RhcnQsbWlkLHF1ZXJ5X3N0YXJ0LHF1ZXJ5X2VuZCk7CgkKCWMgPSBxdWVyeSh0cmVlLDIqdHJlZV9pbmRleCsxLG1pZCsxLGVuZCxxdWVyeV9zdGFydCxxdWVyeV9lbmQpOwoJCgkvLyB5ZWFoIGkga25vdyBpdHMgd3JvbmcgCgkvLyBidXQgY2FuJ3QgZmlndXJlIGl0IG91dCB3aGF0IHRvIGRvIDooCgkvLyAuLi4uLgoJCgkKfQppbnQgbWFpbigpCnsKCWxsIG4saSxqLHgseSxxLGssdmFsOwoJY2luPj5uPj5xPj5rOwoJCglsbCBhWzIqbl0gPSB7MH07Cglmb3IoaSA9IDA7aTxuO2krKykKCQljaW4+PmFbaV0sCgkJYVtuK2ldID0gYVtpXTsKCW5vZGUgdHJlZVs4Km4rNF07CglidWlsZCh0cmVlLGEsMSwwLDIqbi0xKTsKCS8vZm9yKGkgPSAxO2k8PTI2O2krKykKCS8vY291dDw8aTw8Ilx0Ijw8dHJlZVtpXS5hbnM8PCJcdCI8PHRyZWVbaV0ucHJlPDwiXHQiPDx0cmVlW2ldLnN1ZmY8PCJcdCI8PHRyZWVbaV0uaGFzXzA8PGVuZGw7CglqID0gMDsKCQoJCgkKCS8vIGp1c3QgZm9yIHRlc3RpbmcgcHVycG9zZQoJLyp3aGlsZSgxKQoJewoJCS8vY2luPj5qOwoJCS8vY291dDw8ajw8IiAiOwoJCQoJCW5vZGUgbm9kZTEgPSBxdWVyeSh0cmVlLDEsMCxuLTEsIGosaituLTEpOwoJCQoJCWNvdXQ8PGo8PCIgIjw8aituLTE8PCIgIjw8bm9kZTEuYW5zPDwiICI8PG5vZGUxLnByZTw8IiAiPDxub2RlMS5zdWZmPDxlbmRsOwoJCWorKzsKCX0qLwoJCgkKCS8qc3RyaW5nIHF1ZSA9ICIiOwoJY2luPj5xdWU7CglpID0gMDsKCWogPSAwOwoJd2hpbGUoaTxxdWUubGVuZ3RoKCkpCgl7CgkJCgkJaWYocXVlW2ldID09ICchJykKCQl7CgkJCWorKzsKCQkJaWYoaiA9PSBuKQoJCQkJaiA9IDA7CgkJCQoJCX0KCQoJCS8vY291dDw8eDw8IiAiPDx5PDwiXHQiOwoJCWVsc2UKCQl7CgkJCS8vY291dDw8ajw8IiAiPDxqK24tMTw8Ilx0IjsKCQkJdmFsID0gcXVlcnkodHJlZSwxLDAsMipuLTEsIGosaituLTEpLmFuczsKCQkJY291dDw8dmFsPDxlbmRsOwoJCQkvL2NvdXQ8PG1pbihrLHZhbCk8PGVuZGw7CgkJfQoJCQoJCWkrKzsKCX0qLwoJCgkKCQp9