Maximizing Sorted Interval Difference

Given a sequence of n integers \(A_i\) and two indices \(p\) and \(q\) with \(p<q\), you are allowed to choose any contiguous interval \([L,R]\) (with \(1\le L\le p\) and \(q\le R\le n\)) and sort the elements in that interval in non-decreasing order. After the operation, let \(A_p\) and \(A_q\) be the values at indices \(p\) and \(q\) respectively in the modified sequence. Your task is to maximize \(A_q - A_p\) by choosing an appropriate interval \([L,R]\).

Observation: It can be shown that the optimal strategy is to choose \(L=p\) and \(R=q\). In that case, after sorting, \(A_p\) becomes the smallest element and \(A_q\) becomes the largest element of the subarray \(\{A_p, A_{p+1}, \ldots, A_q\}\). Thus, the answer is:

[ \max_{i=p}^{q}A_i - \min_{i=p}^{q}A_i ]

inputFormat

The first line contains three integers \(n\), \(p\), and \(q\) (where \(1 \le n \le 10^5\) and \(1 \le p < q \le n\)).

The second line contains \(n\) integers \(A_1, A_2, \ldots, A_n\) representing the sequence.

outputFormat

Output a single integer, the maximum possible value of \(A_q - A_p\) after performing the operation exactly once.

sample

5 2 4
3 1 9 2 5

8