Periodic Function (Hard)

This problem has different input constraints from Periodic Function (Easy).

A periodic function is a function whose values repeat at regular intervals. If there exists a positive number $p$ such that $f(x+p)=f(x)$ for all $x$, then $f(x)$ is called a periodic function, and $p$ is called a period. A function can have several periods. For example, if $f(x) = \sin x$, then $2n\pi$ can be a period for every positive integer $n$.

Periodic functions make definite integrals easier to compute, because shifting the integration interval by a period does not change the value. For example, the period of $\sin$ is $2\pi$, so $\int_0^\pi \sin x\,dx = \int_{2\pi}^{3\pi} \sin x\,dx$.

Every day, Dooyoung brings Ian a periodic function that Ian does not know, gives him the integral over an arbitrary interval, and asks him to find the integral over another given interval. Tired of solving these by hand, Ian wants a program that computes the answers automatically.

The first line contains the length $L$ of the interval array.

The second line contains $L$ integers separated by spaces. For each integer $i$ with $1 \le i \le L$, the $i$-th number is $\int_{i-1}^i f(x)\,dx$.

The third line contains two integers $a$ and $b$ separated by a space, the endpoints of the interval to find.

Print the value of $\int_a^b f(x)\,dx$ on one line.

• $2 \le L \le 3\times 10^5$
• $-10^9 \le a \le b \le 10^9$
• The absolute value of every integral value is at most $10^9$.
• All input values are integers.
• The length of the period is guaranteed to be an integer at most $\frac{L}{2}$.