A histogram is a polygon made by aligning adjacent rectangles that share a common base line. Each rectangle is called a . The -th bar from the left has width 1 and height .
:::align{center}
Figure: This picture depicts a case when and .
:::
One day, you wanted to find the area of the largest rectangle contained in the given histogram. What you did was to make a list of integers by the following procedure:
For each , calculate the largest area of the rectangle contained in the histogram, where the rectangle's base line coincides with the base line of the -th bar. Add the area to the list .
:::align{center}
Figure: This picture depicts a case when and . The area is 9.
:::
The length of the list is exactly since you chose each pair exactly once. To make your life easier, you sorted the list in non-decreasing order. Now, to find the largest area of the rectangle contained in the histogram, you just need to read the last element of , .
However, you are not satisfied with this at all, so I decided to let you compute some part of the list . You have to write a program that, given two indices and (), calculate the values , i.e. .
输入格式
The first line of the input contains an integer () which is the number of bars in the histogram.
The next line contains space-separated positive integers (), where is the height of the -th bar.
The last line contains two integers and (, ).
输出格式
Print integers. The -th () of them should be the -th element of the list , i.e. .
