cf - 429D

Iahub and Sorin are the best competitive programmers in their town. However, they can't both qualify to an important contest. The selection will be made with the help of a single problem. Blatnatalag, a friend of Iahub, managed to get hold of the problem before the contest. Because he wants to make sure Iahub will be the one qualified, he tells Iahub the following task.

You're given an (1-based) array a with n elements. Let's define function f(i, j) (1 ≤ i, j ≤ n) as (i - j)² + g(i, j)². Function g is calculated by the following pseudo-code:

int g(int i, int j) {
    int sum = 0;
    for (int k = min(i, j) + 1; k <= max(i, j); k = k + 1)
        sum = sum + a[k];
    return sum;
}

Find a value min_i ≠ j f(i, j).

Probably by now Iahub already figured out the solution to this problem. Can you?

Input

The first line of input contains a single integer n (2 ≤ n ≤ 100000). Next line contains n integers a[1], a[2], ..., a[n] ( - 10⁴ ≤ a[i] ≤ 10⁴).

Output

Output a single integer — the value of min_i ≠ j f(i, j).

Example

Input

4
1 0 0 -1

Output

Input

2
1 -1

Output

2

题目分析 ： 首先要对公式进行变形 ， 所给的函数就是让求一个前缀和，那么就是由公式的形式就可得到 (i-j)^2 + (sum[i]-sum[j])^2 , 那么不就是转换成一个平面上的最近两点的距离的平方了吗？

代码示例 ：

const int eps = 1e5+5;

const double pi = acos(-1.0);

const int inf = 1<<29;

#define Max(a,b) a>b?a:b

#define Min(a,b) a>b?b:a

#define ll long long

struct node

{

    ll x, y;

}pre[eps], pt[eps];

bool cmpxy(node a, node b){

    if (a.x == b.y) return a.y < b.y;

    else return a.x < b.x;

}

ll dis(ll i, ll j){

    return (pre[i].x-pre[j].x)*(pre[i].x-pre[j].x)+(pre[i].y-pre[j].y)*(pre[i].y-pre[j].y);

}

ll dis2(ll i, ll j){

    return (pt[i].x-pt[j].x)*(pt[i].x-pt[j].x)+(pt[i].y-pt[j].y)*(pt[i].y-pt[j].y);

}

bool cmpy(node a, node b){

    if (a.y == b.y) return a.x < b.x;

    else return a.y < b.y;

}

ll close_pair(ll l, ll r){

    ll d = 999999999999999;

    if (l == r) return d;

    if (l + 1 == r) return dis(l, r);

    ll m = (l + r) >> 1;

    ll d1 = close_pair(l, m);

    ll d2 = close_pair(m+1, r);

    d = min(d1, d2);

    ll k = 0;

    for(ll i = l; i <= r; i++){

        if ((pre[i].x-pre[m].x)*(pre[i].x-pre[m].x) < d) pt[k++] = pre[i];

    }

    sort(pt, pt+k, cmpy);

    for(ll i = 0; i < k; i++){

        for(ll j = i+1; j < k && (pt[j].y-pt[i].y)*(pt[j].y-pt[i].y) < d; j++){

            ll dd = dis2(i, j);

            d = min(dd, d);

        }

    }

    return d;

}

int main() {

    //freopen("in.txt", "r", stdin);

    //freopen("out.txt", "w", stdout);

    ll n, x;

    cin >> n;

    ll sum = 0;

    for(ll i = 1; i <= n; i++){

        scanf("%lld", &x);

        sum += x;

        pre[i].x = i; pre[i].y = sum;

    }

    sort(pre+1, pre+1+n, cmpxy);

    printf("%lld\n", close_pair(1, n));

    return 0;

}

巴特西

cf - 429D

最新文章

热门文章