题目描述

高端的题目，只需要朴素的题目名称。

定义一个$n$个数字的序列$p_1,p_2,p_3,…,p_n$具有的权值是：

• 当序列的长度$n≤1$时，序列的权值为零。
• 当序列的长度$n>1$时，首先将序列进行排序，之后得到一个不降序的序列，记作$a_1,a_2,a_3,…,a_n$，则序列的权值为：$\sum_{i=1}^{n-1}a_i*a_{i+1}$。即排序后相邻两项乘积的加和。

现在，给你一个初始长度为$n$的数组。你可以从中选择一个允许不连续的子序列（可以为空），显然任意一种选法都可以得到一个子序列的权值。其中两个选取方案是不同的，当且仅当两个子序列选取方案中至少存在一个位置在其中一个方案中出现而另一个没有。

假定所有子序列选取方案概率等同，你的任务是求出任意选取子序列时的权值期望。请将该期望对$(10^9+7)$取模。

本题还没完。现在另外还会给出$q$次修改。每次修改，会改变位置$i$上的数值，变成$x$。你需要在每次修改后求出修改后的数组任意选取子序列时的权值期望。同样对$(10^9+7)$取模。

输入格式

第一行一个整数$n$，表示初始的数组长度为$n$。

接下来一行$n$个正整数，表示初始时数组上的值。

接下来一行一个整数q，表示接下来会有$q$次修改。

接下来$q$行，每行两个空格隔开的整数$i,x$，表示将下标$i(1≤i≤n)$处的数字修改为$x$。

输出格式

第一行输出初始时权值期望取模后的结果。

接下来$q$行，每行一个整数，表示修改后的数组权值期望取模后的结果。

2
1 2
2
1 2
2 1

500000004
1
500000004

样例解释

初始时能选出的子序列有：{}, {1}, {2}, {1, 2}，本例中因为只有两个数字，所以选出的子序列也是连续的，但这不代表不可以选不连续的子序列，请注意。

其权值期望为$(0+0+0+2)/4=1/2$，在模下表示为500000004。

第一次修改后，数组变成[2, 2]，可以选出子序列{}, {2}, {2}, {2, 2}，其期望为(0+0+0+4)/4=1。

第二次修改后，数组变成[2, 1]，可以选出子序列{}, {2}, {1}, {2, 1}，其期望为(0+0+0+2)/4=1/2，在模下表示为500000004。

数据规模与约定

​对于$10\%$的数据，$1 \le n, q \le 10, 1\le a_i, x\le 10^9$；

对于另外$10\%$的数据，$1 \le n \le 10^5, q = 0, 1\le a_i\le 10^9$，且初始的所有$a_i$仅有一个位置上的值与其他不同；

​对于另外$20\%$的数据，$1 \le n \le 10^3, q = 0, 1\le a_i\le 10^9$；

​对于另外$60\%$的数据，$1 \le n, q \le 10^5, 1\le a_i, x\le 10^9$；

大样例

大样例下载