I. Inverted Signs

墨蓝 2022-05-29 02:13 35阅读 0赞

I. Inverted Signs

time limit per test

1.0 s

memory limit per test

256 MB

input

standard input

output

standard output

Arya lives in a magical world. You can view it as a number line.

There are *N* citizens in total. The *i*\-th citizen have his own house in position *i* with height *H**i*, Noted that *H**i* could be non positive, which means their house is actually built beneath the horizon.

Arya is the hand of the king and she thinks that the buildings are a bit out of order. She denote the chaos index of the world as ![4ccf8f93d82d94904c2521d54fcb719b3ee69957.png][].

Noted that *h**i* could be equal to zero as the world is magical.

She feels that the current chaos index of the world is too high. So she designs to change the world a bit by using her super power.

She could flip a continuous sequence of building, i.e., she could choose two arbitrary integer *L* and *R*, where 1 ≤ *L* ≤ *R* ≤ *N*, and invert the signs of *H**i* for all *L* ≤ *i* ≤ *R* (positive to negative and vice versa).

As Arya is weak, she would only do this operation exactly once. Arya wants to minimize the chaos index after the operation. Being a good guy, help Arya to find the lowest possible chaos index after exactly flipping one continuous sequence of building.

Input

The first line contains an integer *N*. (1 ≤ *N* ≤ 106)

The second line consist of *N* integers, the *i*\-th integer is *H**i*. ( - 109 ≤ *H**i* ≤ 109)

Output

Output consist only one integer in a single line, the lowest possible chaos index after exactly flipping one continuous sequence of building.

Examples

input

Copy

4
    1 -2 -3 4

output

input

Copy

5
    -3 -2 0 -5 3

output

Note

In the first sample, Arya should flip house 2 to 3, so that the heights become 1, 2, 3, 4 and the chaos index would be |2 - 1| + |3 - 2| + |4 - 3| = 3.

|*x* - *y*| is the absolute difference between *x* and *y*.

题目解析：

这个题目的意思很简单就是让我们可以调整一个区间的数变成其相反数，然后求每两个相邻数之间和的最小值，很简答

代码：

#include <bits/stdc++.h>
    using namespace std;
    const int maxn = 1e6+1e2;
    typedef long long LL;
    LL a[maxn];
    LL ans[maxn];
    int main()
    {
        //freopen("in.txt","r",stdin);
        int n;
        while(~scanf("%d",&n))
        {
            memset(a,0,sizeof(a));
            memset(ans,0,sizeof(ans));
            LL sum = 0;
            int cnt = 0;
            scanf("%lld",&a[0]);
            for(int i=1; i<n; i++)
            {
                scanf("%lld",&a[i]);
                sum+=abs(a[i]-a[i-1]);
                ans[cnt++] = abs(-a[i]-a[i-1])-abs(a[i]-a[i-1]);
            }
            sort(ans,ans+cnt);
            if(ans[0]<0)
                sum=sum+ans[0];
            if(ans[1]<0)
                sum+=ans[1];
            printf("%lld\n",sum);
        }
    
        return 0;
    }

[4ccf8f93d82d94904c2521d54fcb719b3ee69957.png]: /images/20220529/45d77fd23d73428ca166825062293c7b.png