The problem setter is very busy; they are either rushing to meet a deadline or on their way to meet one. However, the problem setter is also playful and likes to take time out of their busy schedule to uphold justice in Night City.
One day, they arrived at a mysterious neighborhood in Night City. This neighborhood can be viewed as being composed of several $1 \times 1$ squares (blocks) on a grid.
The shape of this neighborhood is quite unique. The lower boundary of the neighborhood is a road of length $n$, which can be divided into $n$ segments on the grid. The $i$-th segment has $a_i$ blocks above it, as shown in the figure below.
Figure 1: Neighborhood
While solving crimes of various sizes in the neighborhood, the problem setter thought of this nonsensical question:
Suppose the problem setter finds a certain type of regional weapon in Night City. They can deploy the weapon on the road at the bottom. The attack range of this weapon is a rectangle; the lower boundary of the rectangle must be flush with the road, and the upper boundary must be flush with one of the upper boundaries of the neighborhood. They want to know, if all possible attack ranges are sorted by area from smallest to largest, what are the areas from the $L$-th largest to the $R$-th largest?
The problem setter is kind and does not want the contestants to read a long problem statement, so they provided a concise version:
Given a sequence $a_1, a_2, \dots, a_n$ of length $n$, let $$f(l, r) = (r - l + 1) \cdot \min_{l \le i \le r} a_i$$ If all $f(l, r)$ ($1 \le l \le r \le n$) are sorted from smallest to largest, find all $f$ values with ranks from $L$ to $R$.
Input
The first line contains a positive integer $n$, representing the length of the sequence $a$. The second line contains $n$ integers, representing $a_1, \dots, a_n$. The third line contains two integers $L$ and $R$, representing the range of ranks to query.
Output
A single line containing $R - L + 1$ integers, where the $i$-th number represents the $f$ value with rank $L + i - 1$.
Examples
Input 1
8 1 5 10 4 7 8 1 2 4 10
Output 1
2 2 2 3 3 3 4
Constraints
- For 20% of the data, $n \le 500$;
- For 40% of the data, $n \le 10000$;
- Additionally, for 20% of the data, $L = R$ is guaranteed;
- For 100% of the data, $n \le 3 \times 10^5$, $a_i \le 10^9$, $1 \le L \le R \le \frac{n(n+1)}{2}$, $R - L + 1 \le 3 \times 10^5$.