D. Almost Difference

 

Let's denote a function

You are given an array a consisting of n integers. You have to calculate the sum of d(a_i, a_j) 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 a₁, a₂, ..., a_n (1 ≤ a_i ≤ 10⁹) — elements of the array.

Output

Print one integer — the sum of d(a_i, a_j) 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(a₁, a₂) = 0;
2. d(a₁, a₃) = 2;
3. d(a₁, a₄) = 0;
4. d(a₁, a₅) = 2;
5. d(a₂, a₃) = 0;
6. d(a₂, a₄) = 0;
7. d(a₂, a₅) = 0;
8. d(a₃, a₄) =  - 2;
9. d(a₃, a₅) = 0;
10. d(a₄, a₅) = 2.

 

哇，好不容易写到第四题，突然弹出消息说这题爆long long，然后就懵逼了，看了下状态AC的全是Python。赛后发现Hacker在疯狂Hack C++，血赚场？

怎么全世界都会long double，不过瞄到qls也被Hack了，窝q(小纠结.JPG)

#include 
      
       using namespace std;map
       
        a; int main(){    int n;    scanf("%d",&n);    long double ans=0;    for (int i=0;i
       
      

q巨赛后补题代码:

#include
      
       using namespace std;typedef long long ll;const int MAXN=200005;const ll BASE=1000000000000000000LL;int a[MAXN];int main(){    int n;    scanf("%d",&n);    ll high=0,low=0;    for(int i=1;i<=n;i++)    {        scanf("%d",&a[i]);        low+=1LL*(2*(i-1)-(n-1))*a[i];        while(low>=BASE)low-=BASE,high++;        while(low<0)low+=BASE,high--;    }    map
       
         mp;    for(int i=1;i<=n;i++)    {        low-=mp[a[i]-1],low+=mp[a[i]+1];        while(low>=BASE)low-=BASE,high++;        while(low<0)low+=BASE,high--;        mp[a[i]]++;    }    if(high>=-1 && high<=0)printf("%lld\n",high*BASE+low);    else if(high>0)printf("%lld%018lld\n",high,low);    else printf("%lld%018lld\n",high+(low>0),(low>0)*BASE-low);    return 0;}