hoj3434

我们把所给数字制成条形统计图，如果确定了最终平面位置，我们把最终平面想象成地面，所有的条形图的上边缘想象成从地面向上或向下长出的山峰。我们的结果就是所有右侧山坡的垂直高度之和加上最右面一点到地面的距离。我们发现在两端点竖直高度值之间平移地面，结果不会有变化。如果移出这个范围，右侧山坡的垂直高度之和不变，而最右边一点到地面的距离会凭空增加。所以地面必然在两端点竖直高度之间。我们只需要计算右侧山峰高度值和即可，不妨把地面定在最左侧点的高度。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
using namespace std;

#define maxn 1000006

int n, f[maxn], p[maxn];
long long sum = 0;
long long ans = 0;

long long min(long long x, long long y)
{
    if (x < y)
        return x;
    return y;
}

void input()
{
    int tot = 1, a;
    scanf("%d", &n);
    scanf("%d", &f[0]);
    for (int i = 1; i < n; i++)
    {
        scanf("%d", &a);
        if (a != f[tot - 1])
            f[tot++] = a;
    }
    n = tot;
}

void work()
{
    for (int i = 1; i < n; i++)
        p[i] = f[i] - f[i - 1];
    sum = 0, ans = 0;
    for (int i = 1; i < n; i++)
    {
        if (sum * p[i] < 0)
            ans += min(abs(sum), abs(p[i]));
        sum += p[i];
    }
    sum = abs(sum);
    ans += sum;
}

int main()
{
    //freopen("D:\\t.txt", "r", stdin);
    int t;
    scanf("%d", &t);
    for (int i = 0; i < t; i++)
    {
        input();
        work();
        printf("Case %d: %I64d %I64d\n", i + 1, ans, sum + 1);
    }
    return 0;
}