## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

# [Solution] Empty Graph Codeforces Solution

D. Empty Graph
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

An array of

$n$ positive integers ${a}_{1},{a}_{2},\dots ,{a}_{n}$ fell down on you from the skies, along with a positive integer $k\le n$.

You can apply the following operation at most $k$ times:

• Choose an index $1\le i\le n$ and an integer $1\le x\le {10}^{9}$. Then do ${a}_{i}:=x$ (assign $x$ to ${a}_{i}$).

Then build a complete undirected weighted graph with $n$ vertices numbered with integers from $1$ to $n$, where edge $\left(l,r\right)$ ($1\le l) has weight $min\left({a}_{l},{a}_{l+1},\dots ,{a}_{r}\right)$.

You have to find the maximum possible diameter of the resulting graph after performing at most $k$ operations.

The diameter of a graph is equal to $\underset{1\le u, where $\mathrm{d}\left(u,v\right)$ is the length of the shortest path between vertex $u$ and vertex $v$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1\le t\le {10}^{4}$).

Solution Click Below:-  👉
👇👇👇👇👇

Description of the test cases follows.

The first line of each test case contains two integers $n$ and $k$ ($2\le n\le {10}^{5}$$1\le k\le n$).

The second line of each test case contains $n$ positive integers ${a}_{1},{a}_{2},\dots ,{a}_{n}$ ($1\le {a}_{i}\le {10}^{9}$).

It is guaranteed that the sum of $n$ over all test cases does not exceed ${10}^{5}$.

Output

For each test case print one integer — the maximum possible diameter of the graph after performing at most $k$ operations.