Maximizing the Guide's Gift

Nanjing has a famous shopping street with neatly arranged stores. Every time, Guide Z leads a group of p tourists to stroll along a segment of the street between store u and store v. In each visited store, the shopping fans buy products in such a way that each tourist buys the same quantity. In other words, if a store has a items and there are p tourists, then each tourist buys \( \lfloor a/p \rfloor \) items, so that the store sells \( p \times \lfloor a/p \rfloor \) items, leaving a remainder of \( a \bmod p \) items.

The store owner, grateful for the business, gives all remaining items (i.e. the remainder) as a gift to Guide Z. Being greedy, Guide Z wants to maximize the number of gifted items. Given the total number of items in each of the n stores (labeled from 0 to n-1), and a query defined by integers p, u and v, your task is to help Guide Z choose one store in the range [u, v] that yields the maximum gift (i.e. maximum \( a \bmod p \)) and output that maximum number.

inputFormat

The input consists of three lines:

1. The first line contains an integer n (the number of stores).
2. The second line contains n space-separated integers representing the number of items in each store.
3. The third line contains three space-separated integers: p (the number of tourists), u, and v representing the inclusive range of store indices that are visited.

You may assume that 0 ≤ u ≤ v ≤ n-1.

outputFormat

Output a single integer which is the maximum number of gifted items (i.e. the maximum value of \( a \bmod p \)) over all stores in the range [u, v].

sample

5
10 13 20 17 8
5 1 3

3