Proficient.
Put your skills to the test.

Problem summary

The measure of an array is the sum of the minimum of every nonempty contiguous subarray. Add the original array measure and the measures of Q independent variants: a variant truncates at ind and replaces that last element with value. Return the total modulo 1000000007.

Constraints

1 ≤ N ≤ 10^6; 0 ≤ Q ≤ 10^5; 1 ≤ a[i], value ≤ 10^5; each ind identifies an array element.

Worked example

An independently prepared example for this explanation.

5
4 7 5 2 3
3
4 2
2 1
0 8

121

Solution analysis

1. Process queries offline by their truncation index. Immediately before processing position i, maintain the measure of the unchanged prefix of length i, and a monotonic stack describing the minima of all suffixes of that prefix.
2. A stack entry (v,j) represents a block of suffix starting positions ending at j, all with minimum v. Stack values increase strictly; the preceding entry ends the preceding block. Store prefix sums of value times block length. Appending value x removes all trailing entries with value at least x, then creates one merged block. This also gives the sum of minima of subarrays ending at the new position.
3. For a query (i,x), all subarrays entirely before i contribute the saved prefix measure. Binary-search the first stack value at least x. Blocks before it retain their minima; every remaining suffix, and the singleton new element, contributes x. For the sample query (2,1), prefix [4,7] has measure 15 and all three new subarrays contribute 1, giving 18. Adding measures 48,47,18,8 gives 121.

Why it works

Inductively the stack partitions every suffix starting position into maximal blocks with equal minimum. Appending x preserves smaller minima and replaces all larger or equal minima by x, exactly the stack update. Each query applies this same transformation without changing the stored original prefix, so its result is the correct independent variant measure. Summing all original ending-position contributions yields the original measure.

Watch out. Queries are independent, not permanent edits. Include the original measure, count the singleton query element, and use 64-bit intermediate sums before reducing modulo 1000000007.

An independently written complete program with standard headers.

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const long long MOD=1000000007;
struct Query{
    int value;
};
struct Block{
    int value;
    int end;
    long long prefix;
};
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    vector<int>values(n);
    for(int&value:values){
        cin>>value;
    }
    int queryCount;
    cin>>queryCount;
    vector<vector<Query>>queries(n);
    while(queryCount--){
        int index,value;
        cin>>index>>value;
        queries[index].push_back({value});
    }
    vector<Block>stack;
    long long measure=0,answer=0;
    for(int i=0;i<n;++i){
        for(const Query&query:queries[i]){
            auto it=lower_bound(stack.begin(),stack.end(),query.value,[](const Block&block,int value){
                return block.value<value;
            });
            int kept=static_cast<int>(it-stack.begin());
            int covered=kept==0?0:stack[kept-1].end+1;
            long long contribution=kept==0?0:stack[kept-1].prefix;
            contribution+=1LL*query.value*(i-covered+1);
            answer=(answer+measure+contribution)%MOD;
        }
        while(!stack.empty()&&stack.back().value>=values[i]){
            stack.pop_back();
        }
        int previousEnd=stack.empty()?-1:stack.back().end;
        long long prefix=stack.empty()?0:stack.back().prefix;
        // The new block includes every suffix whose old minimum was >= values[i].
        prefix+=1LL*values[i]*(i-previousEnd);
        stack.push_back({values[i],i,prefix});
        measure=(measure+prefix)%MOD;
    }
    cout<<(answer+measure)%MOD<<'\n';
}