题目链接

After Mr. B arrived in Warsaw, he was shocked by the skyscrapers and took several photos. But now when he looks at these photos, he finds in surprise that he isn't able to point out even the number of buildings in it. So he decides to work it out as follows: 
- divide the photo into n vertical pieces from left to right. The buildings in the photo can be treated as rectangles, the lower edge of which is the horizon. One building may span several consecutive pieces, but each piece can only contain one visible building, or no buildings at all. 
- measure the height of each building in that piece. 
- write a program to calculate the minimum number of buildings. 
Mr. B has finished the first two steps, the last comes to you.

Input

Each test case starts with a line containing an integer n (1 <= n <= 100,000). Following this is a line containing n integers - the height of building in each piece respectively. Note that zero height means there are no buildings in this piece at all. All the input numbers will be nonnegative and less than 1,000,000,000. 

Output

For each test case, display a single line containing the case number and the minimum possible number of buildings in the photo.

Sample Input

3
1 2 3
3
1 2 1

Sample Output

Case 1: 3
Case 2: 2

Hint

The possible configurations of the samples are illustrated below:

         
  

题意：现在有从左到右n张照片，每张照片上面都有一个建筑，现在给出了每张照片里建筑物的高度（高度一样就可能是同一所建筑），但是可能后面较低的建筑被前面较高的建筑给挡着了，例如：1 3 1，后面的建筑高度为1，但是比较宽占了三张照片，前面高度为1的建筑挡住了后面建筑照片2的那一部分，现在问给出n个高度中，最少能有多少个建筑物。

题解：现在声明一个单调栈维护一个单调序列，要是当前栈不为空且栈顶元素大于当前建筑物高度，建筑物数量+1，因为当前栈维护的是一个递增序列，要是栈顶建筑物高度大于当前高度，那栈顶建筑就是当前最高的，没有其他建筑物能挡着他，所以直接建筑物数量+1，将它弹出栈，要是空栈或者栈顶建筑物小于当前建筑物，说明栈顶建筑物可能被当前建筑物挡着，将当前建筑物压入栈。最后所有枚举完所有建筑物，栈里的建筑物都为单个建筑物直接++就行。

#include <iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<map>
#include<queue>
#include<set>
#include<cmath>
#include<stack>
#include<string>
const int maxn=1e5+10;
const int mod=1e9+7;
const int inf=1e8;
#define me(a,b) memset(a,b,sizeof(a))
#define lowbit(x) x&(-x)
#define mid l+(r-l)/2
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define PI 3.14159265358979323846
int dir[4][2]= {0,-1,-1,0,0,1,1,0};
typedef long long ll;
using namespace std;
int main()
{
    int Case=1,n;
    while(scanf("%d",&n)!=EOF)
    {
        stack<int>q;
        int ans=0;
        for(int i=1;i<=n;i++)
        {
            int x;
            scanf("%d",&x);
            while(!q.empty()&&q.top()>x)
            {
                ans++;
                q.pop();
            }
            if(q.empty()||q.top()<x)
                if(x)
                    q.push(x);
        }
        while(!q.empty())
            q.pop(),ans++;
        printf("Case %d: %d\n",Case++,ans);
    }
    return 0;
}