CF1316F.Battalion Strength

There are $n$ officers in the Army of Byteland. Each officer has some power associated with him. The power of the $i$-th officer is denoted by $p_{i}$. As the war is fast approaching, the General would like to know the strength of the army.

The strength of an army is calculated in a strange way in Byteland. The General selects a random subset of officers from these $n$ officers and calls this subset a battalion.(All $2^n$ subsets of the $n$ officers can be chosen equally likely, including empty subset and the subset of all officers).

The strength of a battalion is calculated in the following way:

Let the powers of the chosen officers be $a_{1},a_{2},\ldots,a_{k}$, where $a_1 \le a_2 \le \dots \le a_k$. The strength of this battalion is equal to $a_1a_2 + a_2a_3 + \dots + a_{k-1}a_k$. (If the size of Battalion is $\leq 1$, then the strength of this battalion is $0$).

The strength of the army is equal to the expected value of the strength of the battalion.

As the war is really long, the powers of officers may change. Precisely, there will be $q$ changes. Each one of the form $i$ $x$ indicating that $p_{i}$ is changed to $x$.

You need to find the strength of the army initially and after each of these $q$ updates.

Note that the changes are permanent.

The strength should be found by modulo $10^{9}+7$. Formally, let $M=10^{9}+7$. It can be shown that the answer can be expressed as an irreducible fraction $p/q$, where $p$ and $q$ are integers and $q\not\equiv 0 \bmod M$). Output the integer equal to $p\cdot q^{-1} \bmod M$. In other words, output such an integer $x$ that $0 \leq x \lt M$ and $x ⋅ q \equiv p \bmod M$).

Byteland 军队中有 $n$ 名军官。每名军官都具有一定的力量值，第 $i$ 名军官的力量值记为 $p_{i}$。由于战争即将爆发，将军希望了解军队的总体实力。

Byteland 军队的实力以一种特殊的方式计算。将军会从这 $n$ 名军官中随机选取一个子集，并称该子集为一个“营”（battalion）。（所有 $2^n$ 个子集——包括空集以及包含全部 $n$ 名军官的子集——被选中的概率均相等。）

一个营的实力按如下方式计算：

设所选军官的力量值为 $a_{1},a_{2},\ldots,a_{k}$，且满足 $a_1 \le a_2 \le \dots \le a_k$。则该营的实力等于

$$a_1a_2 + a_2a_3 + \dots + a_{k-1}a_k.$$

（若营的大小 $\leq 1$，则其实力定义为 $0$。）

军队的总体实力定义为：营的实力的期望值。

由于战争持续时间很长，军官的力量值可能会发生变化。具体而言，将发生 $q$ 次更新操作。每次更新形如 $i$ $x$，表示将 $p_{i}$ 的值修改为 $x$。

你需要计算：军队初始时的实力，以及每次更新操作后的实力。

注意：这些更新是永久生效的。

答案需对 $10^{9}+7$ 取模。形式化地，令 $M = 10^{9}+7$。可以证明，答案总可表示为既约分数 $p/q$，其中 $p, q$ 为整数，且 $q \not\equiv 0 \pmod{M}$。请输出整数 $p \cdot q^{-1} \bmod M$。换言之，请输出唯一满足 $0 \le x < M$ 且 $x \cdot q \equiv p \pmod{M}$ 的整数 $x$。

The first line of the input contains a single integer $n$ ($1 \leq n \leq 3⋅10^{5}$) — the number of officers in Byteland's Army.

The second line contains $n$ integers $p_{1},p_{2},\ldots,p_{n}$ ($1 \leq p_{i} \leq 10^{9}$).

The third line contains a single integer $q$ ($1 \leq q \leq 3⋅10^{5}$) — the number of updates.

Each of the next $q$ lines contains two integers $i$ and $x$ ($1 \leq i \leq n$, $ 1 \leq x \leq 10^{9}$), indicating that $p_{i}$ is updated to $x$ .

输入的第一行包含一个整数 $n$（$1 \leq n \leq 3⋅10^{5}$）—— 表示比特兰军队中军官的数量。

第二行包含 $n$ 个整数 $p_{1},p_{2},\ldots,p_{n}$（$1 \leq p_{i} \leq 10^{9}$）。

第三行包含一个整数 $q$（$1 \leq q \leq 3⋅10^{5}$）—— 表示更新操作的次数。

接下来的 $q$ 行，每行包含两个整数 $i$ 和 $x$（$1 \leq i \leq n$, $ 1 \leq x \leq 10^{9}$），表示将 $p_{i}$ 更新为 $x$。

In the first line output the initial strength of the army.

In $i$-th of the next $q$ lines, output the strength of the army after $i$-th update.

在第一行输出军队的初始战力。

在接下来的 $q$ 行中，第 $i$ 行输出第 $i$ 次更新后军队的战力。

In first testcase, initially, there are four possible battalions

• {} Strength = $0$
• {$1$} Strength = $0$
• {$2$} Strength = $0$
• {$1,2$} Strength = $2$

So strength of army is $\frac{0+0+0+2}{4}$ = $\frac{1}{2}$

After changing $p_{1}$ to $2$, strength of battallion {$1,2$} changes to $4$, so strength of army becomes $1$.

After changing $p_{2}$ to $1$, strength of battalion {$1,2$} again becomes $2$, so strength of army becomes $\frac{1}{2}$.

在第一个测试用例中，初始时存在四种可能的军团：

• {} 强度 = $0$
• {$1$} 强度 = $0$
• {$2$} 强度 = $0$
• {$1,2$} 强度 = $2$

因此，军队的强度为 $\frac{0+0+0+2}{4}$ = $\frac{1}{2}$。

将 $p_{1}$ 修改为 $2$ 后，军团 {$1,2$} 的强度变为 $4$，因此军队的强度变为 $1$。

将 $p_{2}$ 修改为 $1$ 后，军团 {$1,2$} 的强度再次变为 $2$，因此军队的强度变为 $\frac{1}{2}$。