​
#include <iostream>
#include <map>
#include <vector>
#include <string>
using namespace std;
typedef long long ll;
typedef struct lnode
{
	ll l, r;
	struct lnode* left, * right, *parent;
	ll ans;
}node;

node* creat_node(ll l, ll r, ll ans)
{
	node* p = new node;
	p->l = l;
	p->r = r;
	p->ans = ans;
	p->left = p->right = p->parent = NULL;
	return p;
}
node* creat_tree(ll* ans, ll l, ll r)
{
	node* q = creat_node(l, r, ans[r] - ans[l - 1]);
	if (l != r)
	{
		ll mid = (l + r) / 2;
		q->left = creat_tree(ans, l, mid);
		q->right = creat_tree(ans, mid+1, r);
		q->left->parent = q;
		q->right->parent = q;
	}
	return q;
}

void update(node* head, int k)
{
	head->ans += (head->r - head->l + 1) * k;
	if (head->left) update(head->left, k);
	if (head->right) update(head->right, k);
}

void update_p(node* head, int ans)
{
	while (head->parent)
	{
		head->par...