POJ.3250 Bad Hair Day

1.Problem
3250 -- Bad Hair Day (poj.org)

2.Idea
Use monoton stack

3.Source

 int n;  
 Int h[80200];  
 void solve()  
 {       
      int n; cin >> n;  
      for (int i = 0; i < n; i++) {  
           scanf("%d", &h[i]);  
      }  
      h[n] = MOD;  
      Int ans = 0;  
      stack<int> st;//monoton stack  
      for (int i = 0; i <= n; i++) {  
           if (st.empty() || h[st.top()] > h[i])  
                st.push(i);  
           else {  
                while (!st.empty() && h[st.top()] <= h[i]) {  
                     int tmp = st.top(); st.pop();  
                     ans += (Int)(i - tmp - 1);  
                }  
                st.push(i);  
           }  
      }  
      printf("%lld\n", ans);  
 }