inline int Max(int a,int b){return a>b?a:b;}
inline int Lowbit(int a){return a&-a;}
int tree1[200001],tree2[200001],Big;
void addvalue(int key,int v){key+=100000;
     int m;
     if (key%2)m=(tree2[key]+=v);else m=(tree1[key]+=v);
     for (int j=key;j<Big;j+=Lowbit(j+1))tree1[j]=Max(tree1[j],m);
     for (int j=key;j;j-=Lowbit(j))tree2[j]=Max(tree2[j],m);
}
int findMax(int l,int r){l+=100000;r+=100000;
    int j,s;s=-2100000000;
    for (j=r;j-Lowbit(j+1)+1>=l;j-=Lowbit(j+1))s=Max(s,tree1[j]);
    if (l)for (j=l;j+Lowbit(j)-1<=r;j+=Lowbit(j))s=Max(s,tree2[j]);
    return s;
}
void iniTree(){
     Big=200001;
     memset(tree1,0,sizeof(tree1));
     memset(tree2,0,sizeof(tree2));
}