I came up with this problem recently but haven't been able to find an efficient approach. Since it's a self-created problem, I don't have official test cases.

Problem Statement

There is a sequence a of n integers. Process q queries given in order. For q-th query, you are given integers l, r (1 <= l <= r <= n) and a integer x.Perform the following in order: Add x for each of a[l], a[l + 1],.., a[r]. Let m = r - l + 1, and b = (b[1], b[2],.., b[m]) = (a[l], a[l + 1],.., a[r]). For array b you need to perform m — 1 operations. For each operation, select two elements x, y from the array, delete them and add elements x + y to the array with a cost of x + y, find the smallest total cost modulo 1e9 + 7. (n <= 1e5, q <= 1e5, |a[i]| <= 1e9)

I can't think of a specific time limit for this problem either, but can you find the quickest way to solve it?

Update : The addition of x to the values ​​from position l to r in the i-th query will apply to all queries from i + 1 onwards, meaning that after query i, array a becomes a = (a[1], a[2], ..., a[l] + x, a[l + 1] + x, a[r] + x, ..., a[n])

Update 2 : Sorry everyone, I mixed things up a bit while explaining my idea. I've just updated the prompt.