Expected Square Beauty
Contest: Educational Codeforces Round 67 (Rated for Div. 2)
Difficulty rating: 2500
Tags: dp, math, probabilities

Let $$$x$$$ be an array of integers $$$x = [x_1, x_2, \dots, x_n]$$$. Let's define $$$B(x)$$$ as a minimal size of a partition of $$$x$$$ into subsegments such that all elements in each subsegment are equal. For example, $$$B([3, 3, 6, 1, 6, 6, 6]) = 4$$$ using next partition: $$$[3, 3\ |\ 6\ |\ 1\ |\ 6, 6, 6]$$$.

Now you don't have any exact values of $$$x$$$, but you know that $$$x_i$$$ can be any integer value from $$$[l_i, r_i]$$$ ($$$l_i \le r_i$$$) uniformly at random. All $$$x_i$$$ are independent.

Calculate expected value of $$$(B(x))^2$$$, or $$$E((B(x))^2)$$$. It's guaranteed that the expected value can be represented as rational fraction $$$\frac{P}{Q}$$$ where $$$(P, Q) = 1$$$, so print the value $$$P \cdot Q^{-1} \mod 10^9 + 7$$$.

Input format:
The first line contains the single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the size of the array $$$x$$$.

The second line contains $$$n$$$ integers $$$l_1, l_2, \dots, l_n$$$ ($$$1 \le l_i \le 10^9$$$).

The third line contains $$$n$$$ integers $$$r_1, r_2, \dots, r_n$$$ ($$$l_i \le r_i \le 10^9$$$).

Output format:
Print the single integer — $$$E((B(x))^2)$$$ as $$$P \cdot Q^{-1} \mod 10^9 + 7$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
Let's describe all possible values of $$$x$$$ for the first sample:

- $$$[1, 1, 1]$$$: $$$B(x) = 1$$$, $$$B^2(x) = 1$$$;
- $$$[1, 1, 2]$$$: $$$B(x) = 2$$$, $$$B^2(x) = 4$$$;
- $$$[1, 1, 3]$$$: $$$B(x) = 2$$$, $$$B^2(x) = 4$$$;
- $$$[1, 2, 1]$$$: $$$B(x) = 3$$$, $$$B^2(x) = 9$$$;
- $$$[1, 2, 2]$$$: $$$B(x) = 2$$$, $$$B^2(x) = 4$$$;
- $$$[1, 2, 3]$$$: $$$B(x) = 3$$$, $$$B^2(x) = 9$$$;

All possible values of $$$x$$$ for the second sample:

- $$$[3, 4, 5]$$$: $$$B(x) = 3$$$, $$$B^2(x) = 9$$$;
- $$$[3, 4, 6]$$$: $$$B(x) = 3$$$, $$$B^2(x) = 9$$$;
- $$$[3, 5, 5]$$$: $$$B(x) = 2$$$, $$$B^2(x) = 4$$$;
- $$$[3, 5, 6]$$$: $$$B(x) = 3$$$, $$$B^2(x) = 9$$$;
- $$$[4, 4, 5]$$$: $$$B(x) = 2$$$, $$$B^2(x) = 4$$$;
- $$$[4, 4, 6]$$$: $$$B(x) = 2$$$, $$$B^2(x) = 4$$$;
- $$$[4, 5, 5]$$$: $$$B(x) = 2$$$, $$$B^2(x) = 4$$$;
- $$$[4, 5, 6]$$$: $$$B(x) = 3$$$, $$$B^2(x) = 9$$$;

Example input:
3
1 1 1
1 2 3

Example output:
166666673

Example input:
3
3 4 5
4 5 6

Example output:
500000010

Editorial:
As usual with tasks on an expected value, let's denote $$$I_i(x)$$$ as indicator function: $$$I_i(x) = 1$$$ if $$$x_i \neq x_{i - 1}$$$ and $$$0$$$ otherwise; $$$I_1(x) = 1$$$. Then we can note that $$$B(x) = \sum\limits_{i = 1}^{n}{I_i(x)}$$$. Now we can make some transformations: $$$E(B^2(x)) = E((\sum\limits_{i = 1}^{n}{I_i(x)})^2) = E(\sum\limits_{i = 1}^{n}{ \sum\limits_{j = 1}^{n}{I_i(x) I_j(x)} }) = \sum\limits_{i = 1}^{n}{ \sum\limits_{j = 1}^{n}{E(I_i(x) I_j(x))} }$$$.
Now we'd like to make some casework:
• if $$$|i - j| > 1$$$ ($$$i$$$ and $$$j$$$ aren't consecutive) then $$$I_i(x)$$$ and $$$I_j(x)$$$ are independent, that's why $$$E(I_i(x) I_j(x)) = E(I_i(x)) E(I_j(x))$$$;
• if $$$i = j$$$ then $$$E(I_i(x) I_i(x)) = E(I_i(x))$$$;
• $$$|i - j| = 1$$$ need further investigation.
For the simplicity let's transform segment $$$[l_i, r_i]$$$ to $$$[l_i, r_i)$$$ by increasing $$$r_i = r_i + 1$$$.
Let's denote $$$q_i$$$ as the probability that $$$x_{i-1} = x_i$$$: $$$q_i = \max(0, \frac{\min(r_{i - 1}, r_i) - \max(l_{i - 1}, l_i)}{(r_{i - 1} - l_{i - 1})(r_i - l_i)})$$$ and $$$q_1 = 0$$$. Let's denote $$$p_i = 1 - q_i$$$. In result, $$$E(I_i(x)) = p_i$$$.
The final observation is the following: $$$E(I_i(x) I_{i + 1}(x))$$$ is equal to the probability that $$$x_{i - 1} \neq x_i$$$ and $$$x_i \neq x_{i + 1}$$$ and can be calculated by inclusion-exclusion principle: $$$E(I_i(x) I_{i + 1}(x)) = 1 - q_{i} - q_{i + 1} + P(x_{i-1} = x_i\ \&\ x_i = x_{i + 1})$$$, where $$$P(x_{i-1} = x_i\ \&\ x_i = x_{i + 1}) = \max(0, \frac{\min(r_{i-1}, r_i, r_{i+1}) - \max(l_{i-1}, l_i, l_{i+1})}{(r_{i-1} - l_{i-1})(r_i - l_i)(r_{i+1} - l_{i+1})})$$$.
In result, $$$E(B^2(x)) = \sum\limits_{i = 1}^{n}{( p_i + p_i\sum\limits_{|j - i| > 1}{p_j} + E(I_{i-1}(x) I_i(x)) + E(I_i(x) I_{i+1}(x)) )}$$$ and can be calculated in $$$O(n \log{MOD})$$$ time.