#include<bits/stdc++.h>
using namespace std;
const int N=500010;
int a[N];
struct Node{
	int l,r,s;
}tr[N*4];
void build(int x,int l,int r){
	tr[x].l=l;
	tr[x].r=r;
	if(l==r){
		tr[x].s=a[l];
		return;
	}
	int m=(l+r)/2;
	build(2*x,l,m);
	build(2*x+1,m+1,r);
	tr[x].s=tr[2*x].s+tr[2*x+1].s;
}
void add(int x,int pos,int val){
	if(tr[x].l==tr[x].r){
		tr[x].s+=val;
		return;
	}
	int m=(tr[x].l+tr[x].r)/2;
	if(pos<=m)add(2*x,pos,val);
	else add(2*x+1,pos,val);
	tr[x].s-tr[2*x].s+tr[2*x+1].s;
}
int query(int x,int l,int r){
	if(tr[x].l==l&&tr[x].r==r)return tr[x].s;
	if(l>tr[x].r||r<tr[x].l)return 0;
	int m=(tr[x].l+tr[x].r)/2;
	return query(2*x,l,m)+query(2*x+1,m+1,r);
}
int main(){
	
}