Problem Statement

There are N plants in a garden. Each of these plants has been added with some amount of pesticide. After each day, if any plant has more pesticide than the plant at its left, being weaker than the left one, it dies. You are given the initial values of the pesticide in each plant. Print the number of days after which no plant dies, i.e. the time after which there are no plants with more pesticide content than the plant to their left.

Input Format

The input consists of an integer N. The next line consists of N integers describing the array P where P[i] denotes the amount of pesticide in plant i.

Constraints 
1≤N≤100000 
0≤P[i]≤109

Output Format

Output a single value equal to the number of days after which no plants die.

Sample Input

7
6 5 8 4 7 10 9

Sample Output

2

Explanation

Initially all plants are alive. 
Plants = {(6,1), (5,2), (8,3), (4,4), (7,5), (10,6), (9,7)} 
Plants[k] = (i,j) => jth plant has pesticide amount = i. 
After the 1st day, 4 plants remain as plants 3, 5, and 6 die. 
Plants = {(6,1), (5,2), (4,4), (9,7)} 
After the 2nd day, 3 plants survive as plant 7 dies. Plants = {(6,1), (5,2), (4,4)} 
After the 3rd day, 3 plants survive and no more plants die. 
Plants = {(6,1), (5,2), (4,4)} 
After the 2nd day the plants stop dying.

#include<iostream> using namespace std; typedef long long int lli; int arr[1000000]; int ans=0; #include<stack> int main() { int n; cin>>n; for(int i=0;i<n;i++) cin>>arr[i]; stack<pair<int,int> > s; s.push(make_pair(arr[n-1],0)); for(int i=n-2;i>=0;i--) { //cout<<i<<endl; int count=0; while((!s.empty()) && s.top().first>arr[i]) { // cout<<" in stack "<<endl; count=max(count+1,s.top().second); // cout<<"poppinongln "<<s.top().first<<" "<<s.top().second<<endl; s.pop(); } //cout<<" here "<<endl; ans=max(ans,count); s.push(make_pair(arr[i],count)); //cout<<"pusihing "<<arr[i]<<" "<<count<<endl; } cout<<ans<<endl; }

This is a very good implementation. We use a stack to keep all the plants that are not destroyed and the number of day that they are in that state. We approach it from the behind that is from the last element. we iterate from n-1 to 0. at any instant the top of the stack contains the latest tree form the back that is not destoyed. It is important to notice that until and unless the tree is dead we cant go more rightward. Now for every element we arr[i] we compare it with the top of the stack if that(top of the stack) element is greater than the top of the stack then we push arr[i] with 0 to the stack. If the element is less then the top of the stack that means the plant dies and the current value is max(cur+1,weight[stack]). we continue this process till the element is lesser in the stack coz that plant wont die because of this. at the end of this we push this value to the stack. At every iteration the ans is updated as max(ans,cur). dry run the code with the test case 4 6 5 10 11 9 8 7 However it is important observation that the plant that dies is no more present in the day.