Problem Description

Given a sequence $A_i$ of length $n$ and two indices $p, q$ $(p < q)$. You may choose any interval $[L, R]$ and sort the elements in this range, $A_L \sim A_R$, in nondecreasing order.

Find the maximum possible value of $A_q - A_p$ after sorting exactly one chosen interval.

Input Format

The first line contains three integers $n, p, q$, separated by a single space.

The second line contains $n$ integers, representing $A_1, A_2, \cdots, A_n$, separated by a single space.

Output Format

Output one line containing one integer, the maximum value of $A_q - A_p$.

5 1 4
4 5 3 3 1

3

Hint

For $20\%$ of the test cases, $n \le 100$ and $A_i \le 200$.

For $40\%$ of the test cases, $n \le 2000$ and $A_i \le 3000$.

For all test cases, Constraints: $1 \le p \le q \le n \le 2 \times 10^5$, $1 \le A_i \le 10^6$.

Translated by ChatGPT 5