write a go solution for E2. Eliminating Balls With Merging (Hard Version)time limit per test4 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard outputDrink water.— Sun Tzu, The Art of Becoming a Healthy ProgrammerThis is the hard version of the problem. The only difference is that x=1 in this version. You must solve both versions to be able to hack.You are given two integers n and x (x=1). There are n balls lined up in a row, numbered from 1 to n from left to right. Initially, there is a value a_i written on the i-th ball.For each integer i from 1 to n, we define a function f(i) as follows:   Suppose you have a set S=1,2,ldots,i.  In each operation, you have to select an integer l (1<=l<i) from S such that l is not the largest element of S. Suppose r is the smallest element in S which is greater than l.   If a_l>a_r, you set a_l=a_l+a_r and remove r from S.  If a_l<a_r, you set a_r=a_l+a_r and remove l from S.  If a_l=a_r, you choose either the integer l or r to remove from S:   If you choose to remove l from S, you set a_r=a_l+a_r and remove l from S.  If you choose to remove r from S, you set a_l=a_l+a_r and remove r from S.    f(i) denotes the number of integers j (1<=j<=i) such that it is possible to obtain S=j after performing the above operations exactly i-1 times. For each integer i from x to n, you need to find f(i).InputThe first line contains t (1<=t<=10^4) — the number of test cases.The first line of each test case contains two integers n and x (1<=n<=2*10^5;x=1) — the number of balls and the smallest index i for which you need to find f(i).The second line of each test case contains a_1,a_2,ldots,a_n (1<=a_i<=10^9) — the initial number written on each ball.It is guaranteed that the sum of n over all test cases does not exceed 2*10^5.OutputFor each test case, output n-x+1 space separated integers on a new line, where the j-th integer should represent f(x+j-1).ExampleInput35 11 2 3 2 17 14 5 1 2 1 4 511 11 2 3 1 1 9 3 2 4 1 3Output1 1 2 2 3
1 1 1 1 1 3 4
1 1 2 2 2 1 1 1 3 3 4
NoteIn the first test case, below are the possible values of j for each f(i) from 1 to n.  For f(1), the only possible value of j is 1.  For f(2), the only possible value of j is 2.  For f(3), the possible values of j are 2 and 3.  For f(4), the possible values of j are 2 and 3.  For f(5), the possible values of j are 2, 3, and 4.. Output only the code with no comments, explanation, or additional text.