You are given an array A of size N. For each prefix of the A, you have to calculate the value described in the below function.
int func(){
int ans = 0;
for(int i = 0; i <= prefix_index; i++){
int c = 0;
for(int j = 0; j <= prefix_index; j++){
if(A[j] >= A[i]) c++;
}
ans = max(c * A[i], ans);
}
return ans;
}
i.e., in a prefix, the value for the index i is, number of elements greater than or equal to A[i] * A[i]. The answer for the prefix is maximum of these values. The output is a list of N numbers (one for each prefix).
constraints:
1 <= N <= 150000
1 <= A[i] <= 1e9
sample test case:
A = [10, 11, 12, 10, 11, 50, 70]
ans: [10, 20, 30, 40, 50, 60, 100]
test case explanation
I believe this can be solved using segment tree. Solutions without using segment tree will be also interesting. But want to know how to solve using segment tree.
