33091번 - Expected Beauty 다국어

Morgan the robot has an array $A$ of size $N$, indexed from $1$ to $N$. The value of each element in $A$ is randomly generated; $A_i$ can be any integer from $L_i$ to $R_i$ (inclusive) with equal probability.

Morgan defines the beauty of $A$ as follows. First, Morgan has a variable named score that is initialized to $0$. An operation on the array $a$ is as follows:

• Choose an index $i$ such that $1 ≤ i < |a|$ and $a_i = a_{i+1}$. If no such $i$ exists, then the operation cannot be performed.
• Add the value of $a_i$ to score and remove $a_i$ from the array.
• The array $a$ becomes the concatenation of the remaining elements without changing its order.

The beauty of $A$ is the maximum value of score$^2$ Morgan can possibly get after performing zero or more operations on the array $A$.

Since the array is randomly generated, Morgan wonders about the expected beauty of $A$. Due to the inefficiency of his algorithm, Morgan asks for your help to calculate the expected value.

Input begins with an integer $N$ ($1 ≤ N ≤ 200\, 000$) representing the size of array $A$. Each of the next $N$ lines contains two integers $L_i$ $R_i$ ($1 ≤ L_i ≤ R_i ≤ 10^8$).

Let $M = 998\, 244\, 353$. It can be shown that the expected value can be expressed as an irreducible fraction $\frac{p}{q}$, where $p$ and $q$ are integers and $q \not\equiv 0 \bmod M$. Output an integer $x$ in a single line such that $0 ≤ x < M$ and $x \cdot q \equiv p \bmod M$.