D. Almost Difference
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Let's denote a function

You are given an array a consisting of n integers. You have to calculate the sum of d(ai, aj) over all pairs (i, j) such that 1 ≤ i ≤ j ≤ n.

Input

The first line contains one integer n (1 ≤ n ≤ 200000) — the number of elements in a.

The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 109) — elements of the array.

Output

Print one integer — the sum of d(ai, aj) over all pairs (i, j) such that 1 ≤ i ≤ j ≤ n.

Examples
input 
5
1 2 3 1 3
output 
4
input 
4
6 6 5 5
output 
0
input 
4
6 6 4 4
output 
-8
Note

In the first example:

  1. d(a1, a2) = 0;
  2. d(a1, a3) = 2;
  3. d(a1, a4) = 0;
  4. d(a1, a5) = 2;
  5. d(a2, a3) = 0;
  6. d(a2, a4) = 0;
  7. d(a2, a5) = 0;
  8. d(a3, a4) =  - 2;
  9. d(a3, a5) = 0;
  10. d(a4, a5) = 2.

【题意】：计算每个数贡献的值之和。贡献规则如上分段函数所示。

【分析】：假设第i位值是a，那么他的贡献tmp=a*(i-1)-presum。tmp是假设都计算为y-x，presum是前缀和。那最后的贡献就是tmp-cnt(a-1)+cnt(a+1)，相邻的数去掉。因为相邻的数和本身总是相差1，符合分段函数归0部分。前面出现过多少次a-1，a+1，用map实现。

【代码】：

#include <bits/stdc++.h>
using namespace std;
map<double,double>a; 
int main()
{
    int n;
    scanf("%d",&n);
    long double ans=0;
    for (int i=0;i<n;i++)
    {
        double x;scanf("%lf",&x);
        a[x]++;
        ans= ans+ a[x+1]-a[x-1]+x*(i+1-n+i);
    }
    cout << fixed << setprecision(0) << ans << endl;
    return 0;
}
View Code