Given an integer array A[] of size N. The task is to find the maximum of the minimum of every window size in the array. Note: Window size varies from 1 to n.

Given an integer array A[] of size N., The task is to find the maximum of the minimum of every window size in the array.

Note: Window size varies from 1 to n.

In each separate line, print the array of numbers of size N for each of the considered window sizes 1, 2, ..., N respectively.

Input: 

2

7

10 20 30 50 10 70 30

3

10 20 30

Output: 

70 30 20 10 10 10 10 

30 20 10

Explanation:

Testcase 1:

First element in output indicates maximum of minimums of all windows of size 1. Minimums of windows of size 1 are {10}, {20}, {30}, {50}, {10}, {70} and {30}. Maximum of these minimums is 70.

Second element in output indicates maximum of minimums of all windows of size 2. Minimums of windows of size 2 are {10}, {20}, {30}, {10}, {10}, and {30}. Maximum of these minimums is 30.

The third element in the output indicates a maximum of minimums of all windows of size 3. Minimums of windows of size 3 are {10}, {20}, {10}, {10} and {10}. The maximum of these minimums is 20.

Similarly, other elements of output are computed.

#include <bits/stdc++.h>

using namespace std;

int main() {

//code

int t;

cin>>t;

while(t--)

{

    int n,x=0;

    cin>>n;

    int a[n];

    

    for(int i=0;i<n;++i)

    {

    cin>>a[i];

    }

    

    int right[n],left[n],f;

    

    for(int i=0;i<n;++i)

    {

        f=1;

       //finding right smaller than a[i]

        for(int j=i+1;j<n;++j)

        {

            if(a[i]>a[j])

            {

              

                f=0;

                right[i]=j;

                break;

            }

        }

        

        if(f)//if not found  any smaller than place n value

        right[i]=n;

        

        f=1; 

        for(int j=i-1;j>=0;--j)

        {

            if(a[j]<a[i])

            {

                f=0;

                left[i]=j;

                 break;

            }

        }

        

        if(f)left[i]=-1;

    }

   // for(int i=0;i<n;++i)

   // cout<<right[i]<<" ";

   // cout<<endl;

   // for(int i=0;i<n;++i)

   // cout<<left[i]<<" ";

   // cout<<endl;

    int ans[n+1]={0};

    // putting max value of a[i] and ans[len]  at lenght len

    for(int i=0;i<n;++i)

    {

     int len=right[i]-left[i]-1;

     ans[len]=max(ans[len],a[i]);

    }

    

   //  for(int i=0;i<=n;++i)

   // cout<<ans[i]<<" ";

   // cout<<endl;

    // some of not filled and remain zero for that placing from last.

            // max of   ans[i] and a[i+1]

    for(int i=n-1;i>0;--i)

    ans[i]=max(ans[i],ans[i+1]);

    

    

    for(int i=1;i<=n;++i)

       cout<<ans[i]<<" ";

       

        cout<<endl;

        

}

return 0;

}