## Signal Range – Let’s do it guys it’s easy

Various signal range towers are present in a city.Towers are aligned in a straight horizontal line(from left to right) and each tower transmits a signal in the right to left direction.Tower A shall block the signal of Tower B if Tower A is present to the left of Tower B and Tower A is taller than Tower B. So, the range of a signal of a given tower can be defined as :

{(the number of contiguous towers just to the left of the given tower whose height is less than or equal to the height of the given tower) + 1}.

You need to find the range of each tower.

### INPUT

The first line contains an integer T specifying the number of test cases.

The second line contains an integer n specifying the number of towers.

The third line contains n space separated integers(H[i]) denoting the height of each tower.

### OUTPUT

Print the range of each tower (separated by a space).

**Constraints**

1 <= T <= 10

2 <= n <= 10^6

1 <= H[i] <= 10^8

### SAMPLE INPUT

1 7 100 80 60 70 60 75 85

### SAMPLE OUTPUT

1 1 1 2 1 4 6

### Explanation

The 6th tower has a range 4 because there are 3 contiguous towers(3rd 4th and 5th towers) just to the left of the 6th tower whose height is less than the height of the 6th tower.

## Solution with Explanation

```
#include <iostream>
#include<algorithm>
#include<stack>
#include <stdio.h>
#include <math.h>
#include <fstream>
using namespace std;
int ar[1000000];
int main()
{
int n;
cin>>n;
while(n!=0)
{
int l;
cin>>l;
for(int i=0;i<l;i++)
{
cin>>ar[i]; //array to store heights of towers
}
int* span=new int[l]; //array to store the answer
std::stack<int> st; //stack to store INDICES of array "ar"
span[0]=1;
st.push(0);
for(int i=1;i<l;i++)
{
while(!st.empty()&&ar[st.top()]<=ar[i])
{
st.pop(); //pop elements in stack while its non empty and the current height is greater than the height stored at the top of the stack
}
if(st.empty())
span[i]=i+1; //when all elements are popped ,span is simply index+1
else
span[i]=i-st.top(); //span is the difference of indices
st.push(i);
}
for(int i=0;i<l;i++)
{
cout<<span[i]<<" "; //print the answer
}
cout<<"\n";
n--;
}
```

Refer this linkĀ http://www.geeksforgeeks.org/the-stock-span-problem/

to get an idea about efficient solving techniques.

Source-HackerEarth