G1. Big Wins! (easy version)

Problem Statement

This is the easy version of the problem. The difference between the versions is that in this version $a_i \leq \min(n, 100)$.

You are given an array of $n$ integers $a_1, a_2, \ldots, a_n$.

Your task is to find a subarray $a[l,r]$ (a continuous sequence of elements $a_l, a_{l+1}, \ldots, a_r$) for which the value of the expression $\text{med}(a[l,r]) - \min(a[l,r])$ is maximized.

Here:

• $\text{med}$ — the median of the subarray, which is the element at position $\lceil \frac{k+1}{2} \rceil$ after sorting the subarray, where $k$ is its length;
• $\min$ — the minimum element of this subarray.

Example

For example, consider the array $a = [1, 4, 1, 5, 3, 3]$ and choose the subarray $a[2,5] = [4, 1, 5, 3]$. In sorted form, it looks like $[1, 3, 4, 5]$.

• $\text{med}(a[2,5]) = 4$, since $\lceil \frac{4+1}{2} \rceil = 3$, so the third element in the sorted subarray is 4;
• $\min(a[2,5]) = 1$, since the minimum element is 1.

In this example, the value $\text{med} - \min = 4 - 1 = 3$.

Input

The first line contains an integer $t$ $(1 \leq t \leq 10^4)$ — the number of test cases.

The first line of each test case contains one integer $n$ $(1 \leq n \leq 2 \cdot 10^5)$ — the length of the array.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ $(1 \leq a_i \leq \min(n, 100))$ — the elements of the array.

It is guaranteed that the sum of $n$ across all test cases does not exceed $2 \cdot 10^5$.

Output

For each test case, output a single integer — the maximum possible value of $\text{med} - \min$ among all subarrays of the array.

Solution Overview

The problem asks us to find a subarray $a[l, r]$ such that $med(a[l, r]) - min(a[l, r])$ is maximized. The constraint $a_i \le \min(n, 100)$ is crucial here, as it limits the possible values in the array to a small range (1 to 100).

The provided solution leverages this small range of values by iterating through all possible median values.

Here’s a breakdown of the solution:

Understanding the Strategy: Iterating on the Median ($m$)

The core idea is to fix a potential value for the median, let’s call it $m$. Since array values are between 1 and 100, $m$ can also only be between 1 and 100. We will try each of these 100 possible values for $m$.

For a fixed $m$, our goal is to find a subarray $a[l, r]$ such that:

1. $med(a[l, r]) \ge m$ (the median is at least $m$)
2. We want to maximize $m - min(a[l, r])$. This means we want to find a subarray where the median is at least $m$, and its minimum element is as small as possible.

Step-by-Step Explanation for a Fixed Median $m$:

1. Transforming the Array into $b$: For a fixed $m$, we create a new array $b$ of the same size as $a$. Each element $b_j$ is determined as follows:

   • $b_j = +1$ if $a_j \ge m$
   • $b_j = -1$ if $a_j < m$

   Why this transformation? The definition of the median relies on the majority of elements. A subarray $a[l, r]$ will have its median at least $m$ if and only if more than half of its elements are $\ge m$. If we sum the $b_j$ values for a subarray $a[l, r]$, this sum (let’s call it $S$) will tell us about the count of elements greater than or equal to $m$ versus those less than $m$.

   • Each $a_j \ge m$ contributes $+1$ to the sum.
   • Each $a_j < m$ contributes $-1$ to the sum. If the sum $S > 0$, it means there are more elements $\ge m$ than elements $< m$ in the subarray. This ensures that the median of the subarray is at least $m$. (Specifically, for a subarray of length $k$, if the number of elements $\ge m$ is $C_{ge}$ and elements $< m$ is $C_{lt}$, then $S = C_{ge} - C_{lt}$. If $S > 0$, then $C_{ge} > C_{lt}$. Since $C_{ge} + C_{lt} = k$, it implies $C_{ge} > k/2$. This is exactly the condition for the median to be $\ge m$.)

2. Using Prefix Sums for Subarray Sums: We calculate the prefix sums of the $b$ array: $pref_k = \sum_{i=1}^k b_i$. We define $pref_0 = 0$. The sum of $b$ values for a subarray $b[l, r]$ is $pref_r - pref_{l-1}$. So, the condition “$med(a[l, r]) \ge m$” is equivalent to “$pref_r - pref_{l-1} > 0$”, or $pref_r > pref_{l-1}$.

3. Finding “Valid” Indices for Potential Medians: For a fixed $m$, we want to know for each position $j$ if it can be part of some subarray whose median is at least $m$. This is true if there exists a subarray $a[l, r]$ containing $j$ such that $med(a[l, r]) \ge m$. This means we need to check if there’s an $l \le j \le r$ such that $pref_r > pref_{l-1}$.

   The solution states two conditions for this:

   • $min_{0 \le x < j} pref_x < pref_j$: This means there’s a starting point $l-1 = x$ before $j$ such that $pref_j - pref_x > 0$. In other words, there’s a subarray $a[x+1, j]$ ending at $j$ whose median is $\ge m$.
   • $pref_{j-1} < max_{j \le x \le n} pref_x$: This means there’s an ending point $r = x$ at or after $j$ such that $pref_x - pref_{j-1} > 0$. In other words, there’s a subarray $a[j, x]$ starting at $j$ whose median is $\ge m$.

   To efficiently check these conditions for every $j$:

   • Prefix Minima ($prefmn_j$): Compute $prefmn_j = \min_{0 \le x \le j} pref_x$. This allows us to quickly check $min_{0 \le x < j} pref_x < pref_j$.
   • Suffix Maxima ($suffmx_j$): Compute $suffmx_j = \max_{j \le x \le n} pref_x$. This allows us to quickly check $pref_{j-1} < max_{j \le x \le n} pref_x$.

   If either $prefmn_{j-1} < pref_j$ OR $pref_{j-1} < suffmx_j$ (note: the indices might need careful adjustment based on 0-indexing vs 1-indexing, but the concept holds), then position $j$ can be part of a subarray with median $\ge m$.

4. Maximizing $m - a_j$: For each position $j$ that satisfies either of the conditions from step 3 (meaning $a_j$ can be part of a subarray whose median is at least $m$), we consider $a_j$ as a potential minimum element of that subarray. If we pick $a_j$ as the minimum element, and we know there exists a subarray containing $j$ whose median is at least $m$, then we can achieve a value of $m - a_j$. We want to maximize $med - min$. Since we fixed $med \ge m$, to maximize $m - min$, we should try to minimize $min$. The smallest possible $min$ for a subarray that contains $j$ and has its median $\ge m$ is $a_j$ itself, if we choose a subarray $a[l, r]$ where $a_j$ is indeed the minimum.

   The solution says: “If either inequality holds, index $j$ can lie in some subarray whose median is $\ge m$. We are free to take that same $j$ as the minimum of the chosen subarray, giving value $a_j$. Hence, for that $j$ we can realise the gap $m-a_j$. Among all indices that satisfy the test keep the largest difference.” This is a key simplification. It means we don’t need to explicitly find the optimal subarray for each $j$. If $j$ can be part of any valid median $\ge m$ subarray, we assume we can form a subarray where $a_j$ is the minimum, and its median is $\ge m$. This is a greedy approach.

   So, for a fixed $m$, we iterate through all $j$ from $1$ to $n$. If $a_j$ is “valid” (can be part of a subarray with median $\ge m$), we update our maximum difference found so far with $m - a_j$.

Overall Algorithm:

1. Initialize max_difference = -infinity (or a very small number).
2. Iterate m from 1 to 100: a. Create array b where b[j] = +1 if a[j] >= m, else b[j] = -1. b. Compute prefix sums pref for b. (pref[0] = 0, pref[k] = pref[k-1] + b[k]) c. Compute prefix minima prefmn for pref. (prefmn[j] = min(prefmn[j-1], pref[j])) d. Compute suffix maxima suffmx for pref. (suffmx[j] = max(suffmx[j+1], pref[j])) e. Iterate j from 1 to n: i. Check if prefmn[j-1] < pref[j] (subarray ending at $j$ with median $\ge m$). ii. Check if pref[j-1] < suffmx[j] (subarray starting at $j$ with median $\ge m$). iii. If either condition holds, update max_difference = max(max_difference, m - a[j]).
3. Output max_difference.

Complexity:

• Time Complexity:

  • The outer loop runs 100 times (for $m=1$ to $100$).
  • Inside the loop:
    • Building b: $O(n)$
    • Computing pref: $O(n)$
    • Computing prefmn: $O(n)$
    • Computing suffmx: $O(n)$
    • Scanning j and updating max_difference: $O(n)$
  • Total time complexity: $100 \times O(n) = O(100n)$.
  • Given $n \le 2 \cdot 10^5$, $100 \times 2 \cdot 10^5 = 2 \cdot 10^7$, which is well within the 4-second time limit.

• Space Complexity:

  • We need arrays for a, b, pref, prefmn, suffmx, all of size $O(n)$.
  • Total space complexity: $O(n)$.
  • Given $n \le 2 \cdot 10^5$, this fits within 256 megabytes.

Example Walkthrough (Simplified):

Let $a = [1, 4, 1, 5, 3, 3]$

Let’s pick $m=4$.

1. Build $b$ for $m=4$: $a_j \ge 4 \implies b_j = +1$ $a_j < 4 \implies b_j = -1$ $a = [1, 4, 1, 5, 3, 3]$ $b = [-1, +1, -1, +1, -1, -1]$

2. Prefix sums $pref$: ($pref_0=0$) $pref = [0, -1, 0, -1, 0, -1, -2]$ (0-indexed $pref_0$ to $pref_6$)

3. Prefix minima $prefmn$: $prefmn = [0, -1, -1, -1, -1, -1, -2]$

4. Suffix maxima $suffmx$: (assuming $suffmx_{n+1}$ is $-\infty$) $suffmx = [0, 0, 0, 0, 0, -1, -2]$ (from right to left: $\max(-2)$, $\max(-1, -2)$, $\max(0, -1)$, etc.)

5. Iterate $j$ and check validity:

   • For $j=1 (a_1=1)$: $prefmn_0=0, pref_1=-1$. $0 < -1$ is FALSE. $pref_0=0, suffmx_1=0$. $0 < 0$ is FALSE. $a_1$ is not valid for $m=4$.
   • For $j=2 (a_2=4)$: $prefmn_1=-1, pref_2=0$. $-1 < 0$ is TRUE. $a_2$ is valid. $max\_difference = \max(-\infty, 4-4) = 0$.
   • For $j=3 (a_3=1)$: $prefmn_2=-1, pref_3=-1$. $-1 < -1$ is FALSE. $pref_2=0, suffmx_3=0$. $0 < 0$ is FALSE. $a_3$ is not valid.
   • For $j=4 (a_4=5)$: $prefmn_3=-1, pref_4=0$. $-1 < 0$ is TRUE. $a_4$ is valid. $max\_difference = \max(0, 4-5) = 0$.
   • For $j=5 (a_5=3)$: $prefmn_4=-1, pref_5=-1$. $-1 < -1$ is FALSE. $pref_4=0, suffmx_5=-1$. $0 < -1$ is FALSE. $a_5$ is not valid.
   • For $j=6 (a_6=3)$: $prefmn_5=-1, pref_6=-2$. $-1 < -2$ is FALSE. $pref_5=-1, suffmx_6=-2$. $-1 < -2$ is FALSE. $a_6$ is not valid.

For $m=4$, the maximum difference found is $0$.

If we try $m=3$: $a = [1, 4, 1, 5, 3, 3]$ $b = [-1, +1, -1, +1, +1, +1]$ $pref = [0, -1, 0, -1, 0, 1, 2]$ $prefmn = [0, -1, -1, -1, -1, -1, -1]$ $suffmx = [2, 2, 2, 2, 2, 2, 2]$

Let’s check $j=3 (a_3=1)$: $prefmn_2=-1, pref_3=-1$. $-1 < -1$ is FALSE. $pref_2=0, suffmx_3=2$. $0 < 2$ is TRUE. $a_3$ is valid. $max\_difference = \max(\text{current\_max}, 3 - a_3) = \max(\text{current\_max}, 3 - 1) = \max(\text{current\_max}, 2)$.

The solution’s logic is sound and exploits the small range of values in the array to efficiently check all possible median values.

submission