Background

The wedding anniversary of JYY and CX is coming soon, and JYY comes to the gift shop run by Mengmeng to buy a commemorative gift.

Mengmeng’s gift shop is magical: all gifts for sale are arranged in a line in a fixed order, and there is a mysterious sense of beauty between adjacent gifts. So, JYY decides to choose a consecutive segment of gifts, but which ones should be chosen?

Problem Description

Assume the gift shop has $N$ gifts arranged in a line, and each gift has a beauty value. The gift at position $i\ (1\leq i\leq N)$ has a positive integer beauty value $A_i$. JYY decides to choose a consecutive segment, i.e., the gifts numbered $i,i+1,\cdots,j-1,j$. The beauty of the selected gifts is defined as

where $M(i,j)$ denotes $\max\{A_i,A_{i+1},\cdots,A_j\}$, $m(i,j)$ denotes $\min\{A_i,A_{i+1},\cdots,A_j\}$, and $K$ is a given positive integer.

Since JYY does not want to look stingy, the number of gifts selected must be at least $L$. At the same time, selecting too many is hard to carry, so at most $R$ gifts can be selected. How should JYY choose to obtain the maximum beauty value? Since there are too many gifts to choose from, JYY decides to leave this problem to you, who can program.

Input Format

This problem has multiple test cases in each test point.

The first line contains a positive integer $T$, indicating that there are $T$ test cases.

Each test case consists of two lines. The first line contains four non-negative integers $N,K,L,R$. The second line contains $N$ positive integers, in order, representing $A_1,A_2,\cdots,A_n$.

Output Format

Output $T$ lines. Each line contains a non-negative real number, corresponding to the answer for each test case. The testdata guarantees that the answer will not exceed $10^3$. Output the value rounded to $4$ decimal places.

1
5 1 2 4
1 2 3 4 5

0.7500

Hint

For $100\%$ of the testdata, $T\leq 10$, $N,K\leq 5\times 10^4$, $1\leq A_i\leq 10^8$, $2\leq L,R\leq N$.

Translated by ChatGPT 5