P10991 [Lanqiao Cup 2023 National Python A] Segment Sorting

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.

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 one line containing one integer, the maximum value of $A_q - A_p$.

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