G1. Большие выигрыши! (простая версия)
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это простая версия задачи. Отличие между версиями заключается в том, что в этой версии $$$a_i \leq \min(n,100)$$$.

Вам дан массив из $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$.

Ваша задача — найти такой подмассив $$$a[l, r]$$$ (непрерывную последовательность элементов $$$a_l, a_{l + 1}, \dots, a_r$$$), для которого значение выражения $$$\text{med}(a[l, r]) - \min(a[l, r])$$$ максимально.

Здесь:

  • $$$\text{med}$$$ — медиана подмассива, то есть элемент, стоящий на позиции $$$\left\lceil \frac{k + 1}{2} \right\rceil$$$ после сортировки подмассива, где $$$k$$$ — его длина;
  • $$$\min$$$ — минимальный элемент этого подмассива.

Например, рассмотрим массив $$$a=[1, 4, 1, 5, 3, 3]$$$ и выберем подмассив $$$a[2, 5] = [4, 1, 5, 3]$$$. В отсортированном виде он выглядит как $$$[1, 3, 4, 5]$$$.

  • $$$\text{med}(a[2, 5]) = 4$$$, так как $$$\left\lceil \frac{4 + 1}{2} \right\rceil = $$$ третий элемент в отсортированном подмассиве равен $$$4$$$;
  • $$$\min(a[2, 5]) = 1$$$, так как минимальный элемент равен $$$1$$$.

В данном примере значение $$$\text{med} - \min = 4 - 1 = 3$$$.

Входные данные

Первая строка содержит целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — длину массива.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq \min(n, 100)$$$) — элементы массива.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.

Выходные данные

На каждый набор входных данных выведите одно целое число — максимальное возможное значение $$$\text{med} - \min$$$ среди всех подмассивов массива.

Пример
Входные данные
5
5
3 2 5 3 1
4
4 1 1 3
7
6 1 3 4 6 2 7
4
4 2 3 1
5
1 2 3 4 5
Выходные данные
3
3
5
2
2
Примечание

В первом примере рассмотрим массив: $$$a=[3,\ 2,\ 5,\ 3,\ 1]$$$ можно выбрать подмассив $$$a[2,\ 3]$$$, то есть элементы $$$[2,\ 5]$$$.

  • Длина подмассива равна $$$2$$$.
  • Медиана — это элемент на позиции $$$\left\lceil \dfrac{3}{2} \right\rceil = 2$$$ в отсортированном подмассиве. После сортировки получаем $$$[2,\ 5]$$$, $$$\text{med} = 5$$$.
  • Минимальный элемент подмассива: $$$\min = 2$$$.

Следовательно, $$$\text{med} - \min = 5 - 2 = 3$$$, что и является максимальным ответом.

Во втором тесте массив: $$$a=[4,\ 1,\ 1,\ 3]$$$ можно выбрать подмассив $$$a[1,\ 2]$$$, то есть элементы $$$[4,\ 1]$$$.

  • Длина подмассива равна $$$2$$$.
  • Медиана — это элемент на позиции $$$\left\lceil \dfrac{3}{2} \right\rceil = 2$$$ в отсортированном подмассиве. После сортировки получаем $$$[1,\ 4]$$$, $$$\text{med} = 4$$$.
  • Минимальный элемент подмассива: $$$\min = 1$$$.

Следовательно, $$$\text{med} - \min = 4 - 1 = 3$$$.

Можно доказать, что оба этих подмассива являются оптимальными и дают максимальное значение выражения $$$\text{med} - \min$$$.