# PROBLEM LINKS

## DIFFICULTY

MEDIUM

## PREREQUISITES

Simple Math

## PROBLEM

You are given a sequence of **random** integers A_{1}, A_{2}, …, A_{N}. Compute the product of max(A_{i}, A_{i+1}, …, A_{j}) - min(A_{i}, A_{i+1}, …, A_{j}) over all 1 ≤ i < j ≤ N, modulo 1,000,000,007.

## QUICK EXPLANATION

Let ans[j] be the answer to the problem for subsequence A_{1}, A_{2}, …, A_{j}; i.e., ans[j] = diff(1, j) × diff(2, j) × … diff(j-1, j), where diff(i, j) = max(A_{i}, A_{i+1}, …, A_{j}) - min(A_{i}, A_{i+1}, …, A_{j}). Then, the actual answer is ans[1] × ans[2] × … × ans[N]. The value of ans[j+1] can be calculated from ans[j] in O(1) amortized time since the array is random.

## EXPLANATION

In this solution, we will add the elements of A one-by-one. Let’s consider subsequence A_{1}, A_{2}, …, A_{j} and solve it. To do this, we will maintain two additional arrays M[] and m[], where:

- M[i] = max(A
_{i}, A_{i+1}, ..., A_{j}) - m[i] = min(A
_{i}, A_{i+1}, ..., A_{j})

For example, let A = (3, 6, 5, 1, 5, 3, 4). (Here, j = 7.) Then,

- M = (6, 6, 5, 5, 5, 4, 4)
- m = (1, 1, 1, 1, 3, 3, 4)

It is obvious that the elements of M are sorted in non-increasing order, while the elements of m are sorted in non-decreasing order.

Let diff(i, j) = max(A_{i}, A_{i+1}, …, A_{j}) - min(A_{i}, A_{i+1}, …, A_{j}). Suppose we know the answer for this subproblem; i.e., we have calculated ans[j] = the product of diff(i2, j2) for all 1 ≤ i2 < j2 ≤ j. Let’s add element A_{j+1}. Now, we want calculate the subproblem A_{1}, A_{2}, …, A_{j+1}. It can be seen that

ans[j+1] = ans[j] × {diff(1, j+1) × diff(2, j+1) × … × diff(j, j+1)}

The value of {diff(1, j+1) × diff(2, j+1) × … × diff(j, j+1)} can be calculated efficiently using the M and m arrays above. First, as we now have a new element A_{j+1}, let’s update M and m but do not add new elements to them yet. For example, suppose A_{j+1} = 5. Then,

- M = (6, 6, 5, 5, 5,
**5**,**5**) - m = (1, 1, 1, 1, 3, 3, 4)

On the other hand, suppose A_{j+1} = 2. Then,

- M = (6, 6, 5, 5, 5, 4, 4)
- m = (1, 1, 1, 1,
**2**,**2**,**2**)

In the other words, when we introduce a new element A_{j+1}, either the last several elements of M or m will be updated. Let k be the index of the first element of either M or m that is updated; i.e., if A_{j+1} = 5 then k = 6, while if A_{j+1} = 2 then k = 5 as shown on the above examples. Then, diff(i, j) = diff(i, j+1) for all i < k since the minimum and the maximum will remain equal. Therefore,

ans[j+1] = ans[j] × {diff(1, j) × diff(2, j) × … × diff(k-1, j)} × {diff(k, j+1) × diff(k+1, j+1) × … × diff(j-1, j+1)}

The value of {diff(1, j) × diff(2, j) × … × diff(k-1, j)} can be calculated in O(1) time by precalculating and maintaining the prefix product prod[i] = diff(1, j) × diff(2, j) × … × diff(i, j). The value of {diff(k, j+1) × diff(k+1, j+1) × … × diff(j, j+1)} can be calculated in a single loop form k to j as:

diff(k, j+1) × diff(k+1, j+1) × … × diff(j, j+1) = (M[k] - m[k]) × (M[k+1] - m[k+1]) × … × (M[j] - m[j]).

However, since the input array is random, one can prove that the total number operations for calculating the above expression for 1 ≤ j ≤ N is O(N lg N), not O(N^{2}). Therefore, the overall complexity of this algorithm is O(N lg N).

Here is a pseudocode of this algorithm. Note that all operations should be performed modulo 1,000,000,007.

read(N) M[0] = infinity m[0] = -infinity prod[0] = 1 res = 1 for j = 1; j ≤ N; j++: read(A[j]) k = j-1 // update M while A[j] > M[k]: M[k] = A[j] k-- // update m while A[j] < m[k]: m[k] = A[j] k-- k++ // update prod for i = k; i ≤ j; i++: prod[i] = prod[i-1] × (M[k] - m[k]) // update M and m M[j] = m[j] = A[j] // update answer res = res * prod[j]; println(res)

## SETTER’S SOLUTION

Can be found here.

## TESTER’S SOLUTION

Can be found here.

The tester uses different algorithm that will be explained below.

### RMQ Data Structure

In this solution, we need to find the maximum and the minimum element of A_{i}, A_{i+1}, …, A_{j} efficiently. We could use segment tree data structure. However, since the sequence is static we can use RMQ (Range Min/Max Query) that is simpler to code.

Suppose we want to build Range Max Query data structure (the Range Min Query version is similar). Let rmq[i][j] = x such that A_{x} = max(A_{i}, A_{i+1}, …, A_{i+2j-1}). This RMQ table can be filled as follows.

- rmq[i][0] = i
- rmq[i][j] = rmq[i][j-1] if A
_{rmq[i][j-1]}> A_{rmq[i+2j-1][j-1]}, or rmq[i+2^{j-1}][j-1] otherwise

This RMQ table can be built in O(N lg N) time and space complexity.

Now, the maximum element of A_{i}, A_{i+1}, …, A_{j} can be found in O(1) time. Let k = maximum integer such that 2^{k} ≤ j-1+1. Then,

max(A_{i}, A_{i+1}, …, A_{j}) = max(A_{rmq[i][k]}, A_{rmq[j-2k+1][k]}).

The value of k for each value j-i+1 can be precomputed in at most O(N lg N) time so that it can be retrieved in O(1) time.

### Modular Multiplicative Inverse

In this solution, we need a division modulo M = 1,000,000,007. Since M is a prime number, we can use Fermat’s little theorem:

A / B mod M = A × B^{-1} mod M = A × B^{M-2} mod M.

The value of B^{M-2} mod M can be calculated in O(lg M) time using exponentiation by squaring.

### Solution

Now let’s discuss the actual solution. We will use dynamic programming approach. Let dp[i][j] = the answer for the subproblem A_{i}, A_{i+1}, …, A_{j}, i.e. the product of max(A_{i2}, A_{i2+1}, …, A_{j2}) - min(A_{i2}, A_{i2+1}, …, A_{j2}) over all i ≤ i2 < j2 ≤ j. Use the RMQ data structure to retrieve indices p and q such that

- A
_{p}= max(A_{i}, A_{i+1}, ..., A_{j}) - A
_{q}= min(A_{i}, A_{i+1}, ..., A_{j})

Suppose s = max(p, q) and t = min(p, q). We can illustrate the positions of the indices in the below ASCII art.

+-+-+-+ +-+ +-+ +-+-+-+-+ | | | | ... | | ... | | ... | | | | | +-+-+-+ +-+ +-+ +-+-+-+-+ i t s j

Let’s count the number of ranges [i2, j2] that covers indices p and q. Those ranges will then have the maximum value of A_{p} and the minimum value of A_{q}. From the above image, the valid ranges [i2, j2] are such that i ≤ i2 ≤ t; s ≤ j2 ≤ j. There are (t-i+1) × (j-s+1) such ranges. Therefore, the value (A_{p} - A_{q}) will be multiplied (t-i+1) × (j-s+1) times.

There are remaining ranges that have not been considered yet, namely ranges such that i ≤ i2 < j2 ≤ s-1 and ranges such that t+1 ≤ i2 < j2 ≤ j. But they are just subproblems of the original problems! The values are dp[i][s-1] and dp[t+1][j], respectively. However, we will consider the ranges such that t+1 ≤ i2 < j2 ≤ s-1 twice. We can fix this by dividing the result by dp[t+1][s-1].

In summary,

dp[i][j] = (A_{p} - A_{q})^{(j-s+1) × (t-i+1)} × dp[i][s-1] × dp[t+1][j] / dp[t+1][s-1].

Because we only consider ranges that have at least 2 elements, the base case is dp[i][i] = multiplicative identity = 1 for all 1 ≤ i ≤ N.

### Random Array

Now, it seems that we will need O(N^{2}) memory to store the DP table, which is too much as N can be up to 100,000. However, there is an important constraint: all elements are generated independently and uniformly at random. It can be proved that the number of states for such arrays is at most 2 × N. Therefore, we can use top-down approach for filling the DP table and store only visited states in a map or hash table. The time complexity of this solution is therefore O(N lg N) and the space complexity is O(N).