409774: GYM103741 D Difference

Walk_alone has a sequence $$$a$$$ of length $$$n$$$, he defines function $$$f$$$ as $$$$$$ f(l,r)=\big(\max_{l \leq i \leq r} a_i -\min_{l \leq i \leq r}a_i\big)(r-l+1) $$$$$$

He thinks that calculating the value of the function to a given interval is too boring, so he wants you to output the $$$k$$$-th largest value of the function among all $$$f(l,r)$$$ where $$$1 \leq l \leq r \leq n$$$.

The first line contains $$$n\ (1\leq n\leq 5\cdot 10^5)$$$ and $$$k\ (1\le k\le n(n+1)/2)$$$, where $$$n$$$ indicates the length of sequence $$$a$$$.

The second line contains $$$n$$$ integers $$$a_1,a_2,\dots, a_n\ (|a_i|\le 10^9)$$$ as the sequence.

Output a single value indicating the $$$k$$$-th largest function value among all intervals.

3 2
3 1 2

4