struct Node
{
　 int data;
　 int addMark;
};
void PushDown(Node* tree,int pos)
{
　 if (tree[pos].addMark == 0) return;
　 tree[pos * 2 + 1].data += tree[pos].addMark;
　 tree[pos * 2 + 2].data += tree[pos].addMark;
　 tree[pos * 2 + 1].addMark += tree[pos].addMark;
　 tree[pos * 2 + 2].addMark += tree[pos].addMark;
　tree[pos].addMark = 0;
}
void BuildTree(Node* tree,int root,int a[],int s,int e)
{
　 if (s + 1 >= e)
　{
　　 tree[root].addMark = 0;
　　 tree[root].data = a[s];
　　 return;
　}
　 int mid = (s + e) / 2;
　BuildTree(tree, 2 * root + 1, a, s, mid);
　BuildTree(tree, 2 * root + 2, a, mid, e);
　tree[root].data = MAX(tree[2 * root + 1].data, tree[2 * root + 2].data);
}
int Query(Node* tree,int root,int s,int e,int qs,int qe)
{
　 if (qe <= s || qs >= e) return -1;
　 if (qs <= s&&qe >= e) return tree[root].data;
　PushDown(tree, root);
　 int mid = (s + e) / 2;
　int lmax=Query(tree, 2 * root + 1, s, mid, qs, qe);
　 int rmax=Query(tree, 2 * root + 1, s, mid, qs, qe);
　return lmax > rmax ? lmax : rmax;
}
void Update(Node* tree,int root,int s,int e,int us,int ue,int v)
{
　 if (ue <= s || us >= e) return;
　if (us >= s&&ue <= e)
　{
　　 tree[root].addMark += v;
　　 tree[root].data += v;
　　return;
　 }
　PushDown(tree, root);
　 int mid = (s + e) / 2;
　Update(tree, 2 * root + 1, s, mid, us, ue,v);
　 Update(tree, 2 * root + 1, s, mid, us, ue,v);
　 tree[root].data = MAX(tree[2 * root + 1].data, tree[2 * root + 2].data);
}