SOLVE
LATER
Micro and Mike are doing some research on arrays. For experiment purpose, they purchased an array $$A$$ having $$N$$ integers. They have a board which displays Health of their array.
Health of an array is defined as sum of fitness-factor for all possible non-empty sub-sequences of the array. Fitness-factor of a non-empty sub-sequence is defined as product of maximum and minimum element present in the sub-sequence.
An array $$P$$ is called subsequence of another array $$Q$$, if $$P$$ can be obtained by deleting zero or more elements of $$Q$$.
They want the value on the board to get updated each time they change any element of the array. They've written a program for it. Their program takes the array as input, then allows them to perform $$Q$$ operations. Each operation is defined as:
$$x \; v$$: Change $$A[x]$$ to $$v$$.
After each operation their program prints the Health of the new array. But they are not sure that their program is correct. So, they want you to write a program that performs the same task, so that they can compare their output against yours.
Input:
First line consists of two space separated integers denoting $$N$$ and $$Q$$.
Second line consists of $$N$$ space separated integers denoting the array $$A$$.
Each of the following $$Q$$ lines consists of a single operation as defined.
Output:
After performing each operation print the health of the new array in a new line. Since output can be large, print it modulo $$10^9+7$$.
Constraints:
$$1 \le N \le 10^5$$
$$1 \le Q \le 2 \times 10^5$$
$$1 \le A[i], v \le 10^9$$
$$1 \le x \le N$$
After performing $$1^{st}$$ operation array will be $$[1, 4, 3]$$. All possible sub-sequences along with their fitness factor are:
$$[1]$$ - $$1$$
$$[4]$$ - $$16$$
$$[3]$$ - $$9$$
$$[1, 4]$$ - $$4$$
$$[1, 3]$$ - $$3$$
$$[4, 3]$$ - $$12$$
$$[1, 4, 3]$$ - $$4$$
Now, health of the array is sum of fitness factor of all sub-sequences which is $$49$$.
After performing $$2^{nd}$$ operation array will be $$[3, 4, 3]$$. All possible sub-sequences along with their fitness factor are:
$$[3]$$ - $$9$$
$$[4]$$ - $$16$$
$$[3]$$ - $$9$$
$$[3, 4]$$ - $$12$$
$$[3, 3]$$ - $$9$$
$$[4, 3]$$ - $$12$$
$$[3, 4, 3]$$ - $$12$$
Now, health of the array is sum of fitness factor of all sub-sequences which is $$79$$.