write a go solution for G1. Big Wins! (easy version)time limit per test4 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputThis is the easy version of the problem. The difference between the versions is that in this version a_i<=min(n,100).You are given an array of n integers a_1,a_2,...,a_n.Your task is to find a subarray a[l,r] (a continuous sequence of elements a_l,a_l+1,...,a_r) for which the value of the expression med(a[l,r])-min(a[l,r]) is maximized.Here:   med — the median of the subarray, which is the element at position ceil(k+1/2) after sorting the subarray, where k is its length;  min — the minimum element of this subarray. 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].  med(a[2,5])=4, since ceil(4+1/2)= 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 med-min=4-1=3.InputThe first line contains an integer t (1<=t<=10^4) — the number of test cases.The first line of each test case contains one integer n (1<=n<=2*10^5) — the length of the array.The second line of each test case contains n integers a_1,a_2,...,a_n (1<=a_i<=min(n,100)) — the elements of the array.It is guaranteed that the sum of n across all test cases does not exceed 2*10^5.OutputFor each test case, output a single integer — the maximum possible value of med-min among all subarrays of the array.ExampleInput553 2 5 3 144 1 1 376 1 3 4 6 2 744 2 3 151 2 3 4 5Output3
3
5
2
2
NoteIn the first example, consider the array: a=[3,2,5,3,1] you can choose the subarray a[2,3], which consists of the elements [2,5].  The length of the subarray is 2.  The median is the element at position ceil(dfrac32)=2 in the sorted subarray. After sorting, we get [2,5], med=5.  The minimum element of the subarray: min=2. Therefore, med-min=5-2=3, which is the maximum answer.In the second test, the array: a=[4,1,1,3] you can choose the subarray a[1,2], which consists of the elements [4,1].  The length of the subarray is 2.  The median is the element at position ceil(dfrac32)=2 in the sorted subarray. After sorting, we get [1,4], med=4.  The minimum element of the subarray: min=1. Therefore, med-min=4-1=3.It can be proven that both of these subarrays are optimal and yield the maximum value of the expression med-min.. Output only the code with no comments, explanation, or additional text.