Para una permutación de $1, 2, \ldots, n$, sea $s_i$ la longitud del subarreglo contiguo más corto que contiene todos los valores $1, 2, \ldots, i$.
Sea $\operatorname{pos}_p(x)$ la posición de $x$ en la permutación; se cumple que
$$ s_i = \max_{1 \le x \le i} \operatorname{pos}_p(x) - \min_{1 \le x \le i} \operatorname{pos}_p(x) + 1. $$
Para cada $i$, se da una restricción en forma de intervalo $[l_i, r_i]$.
Cuenta las permutaciones que satisfacen $l_i \le s_i \le r_i$ para todo $i$. Imprime la respuesta módulo $998244353$.
Entrada
La primera línea contiene un entero $n$ ($1 \le n \le 2 \cdot 10^5$).
Cada una de las siguientes $n$ líneas contiene dos enteros $l_i$ y $r_i$ ($1 \le l_i \le r_i \le n$).
Salida
Imprime el número de permutaciones válidas módulo $998244353$.
Ten en cuenta que puede no existir ninguna permutación válida.
Ejemplos
Entrada 1
3 1 1 2 2 3 3
Salida 1
4
Nota
Las permutaciones válidas del ejemplo son $(1, 2, 3)$, $(2, 1, 3)$, $(3, 1, 2)$ y $(3, 2, 1)$.