← 返回题目列表

Codeforces · 2126/G1

G1. 大胜利! (简易版)

中文机器翻译题面 查看原题

这是问题的简单版本。版本之间的区别在于,在此版本中 $$$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$$$ 的最大值。