Let's denote a function 

$d(x, y) = \left\{\begin{array}{ll}{y - x,} & {\text{if}|x - y|> 1} \\{0,} & {\text{if}|x - y|\leq 1} \end{array} \right.$

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_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^9) — 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:

  d(a_1, a_2) = 0;  d(a_1, a_3) = 2;  d(a_1, a_4) = 0;  d(a_1, a_5) = 2;  d(a_2, a_3) = 0;  d(a_2, a_4) = 0;  d(a_2, a_5) = 0;  d(a_3, a_4) =  - 2;  d(a_3, a_5) = 0;  d(a_4, a_5) = 2.

Difficulty: interview

Starter code:

Solutions:
n = int(input())
line = list(map(int, input().split()))
m = dict()
ans = 0
for i in range(n):
    if line[i] not in m:
        m[line[i]] = 1
    else:
        m[line[i]] += 1
    var = m[line[i]]
    if line[i] - 1 in m:
        var += m[line[i]-1]
    if line[i] + 1 in m:
        var += m[line[i]+1]
    ans += (i+1-var) * line[i]
x = dict()
for j in range(n):
    i = n - j - 1
    if line[i] not in x:
        x[line[i]] = 1
    else:
        x[line[i]] += 1
    var = x[line[i]]
    if line[i] - 1 in x:
        var += x[line[i]-1]
    if line[i] + 1 in x:
        var += x[line[i]+1]
    ans -= (j+1-var) * line[i]
print(ans)



summ = 0
glob = 0
N = int(input())
a = {}
cnt = 0
huh = list(map(int, input().split()))
for i in huh:
    if i - 1 not in a:
        a[i - 1] = 0
    if i + 1 not in a:
        a[i + 1] = 0
    if i not in a:
        a[i] = 0
    glob += (cnt - a[i - 1] - a[i + 1]) * i - (summ - a[i - 1] * (i - 1) - a[i + 1] * (i + 1))
    a[i] += 1
    summ += i
    cnt += 1
print(glob)

from collections import Counter
from itertools import accumulate as acc
read=lambda: list(map(int,input().split()))
n=int(input())
x=read()
s=0
ans=0
c=Counter()
for num,i in enumerate(x):
    ans+=(num-c[i-1]-c[i+1])*i-(s-c[i-1]*(i-1)-c[i+1]*(i+1))
    c[i]+=1
    s+=i
print(ans)


def ii():
    return int(input())
def mi():
    return list(map(int, input().split()))
def li():
    return list(mi())
from collections import defaultdict

n = ii()
a = li()

def calc(a):
    d = defaultdict(int)
    s = 0
    for i in range(n):
        x = a[i]
        s += (i - d[x] - d[x-1] - d[x+1]) * x
        d[x] += 1
    return s

ans = calc(a) - calc(a[::-1])
print(ans)


n = int(input())
array = list(map(int, input().split()))

d = dict()
t, c = 0, 0

for i in range(len(array)):
    c += array[i]
    t += (i + 1) * array[i] - c

    if array[i] in d:
        d[array[i]] += 1
    else:
        d[array[i]] = 1

    if (array[i] + 1) in d:
        t += d[array[i] + 1]
    if (array[i] - 1) in d:
        t -= d[array[i] - 1]

print(t)


n = int(input())
a = list(map(int, input().split()))

ps = a[0]
ans = 0
h = {a[0]:1}
hv = {a[0]: a[0]}
def gv(h, k):
    if k in h:
        return h[k]
    else:
        return 0

for i in range(1, n):
    c = i - gv(h,a[i]) - gv(h,a[i]-1) - gv(h,a[i]+1)
    cps = ps - gv(hv,a[i]) -gv(hv,a[i]-1)-gv(hv,a[i]+1)
    ans += a[i]*c - cps
    #print(a[i], c, cps)
    #print(ans)
    if a[i] not in h:
        h[a[i]] = 0
        hv[a[i]] = 0
    h[a[i]] += 1
    hv[a[i]] += a[i]
    ps += a[i]
print(ans)

n = int(input())
t = list(map(int, input().split()))
c = {}
u = {}
a = [0 for _ in range(n)]
for i in range(n):
    a[i] = t[i]*i - t[i]*(n-1-i);
    if t[i] not in u:
        u[t[i]] = [i]
    else:
        u[t[i]].append(i)
l = []
for x in u:
    l.append(x);
l.sort()
p = len(l)
res = 0
for i in range(p-1):
    if (l[i]+1 in u):
        l1 = len(u[l[i]])
        l2 = len(u[l[i]+1])
        j1 = 0
        j2 = 0
        t1 = 0
        t2 = 0
        for j in range(l1+l2):
            #print(j1, j2);
            #print(l1, l2)
            if (j1 == l1):
                t2 += 1
                j2 += 1
                res -= t1
            elif j2 == l2:
                t1 += 1
                j1 += 1
                res += t2
            elif (u[l[i]][j1] < u[l[i]+1][j2]):
                t1 += 1
                j1 += 1
                res += t2
            else:
                t2 += 1
                j2 += 1
                res -= t1
for i in range(n):
    res += a[i]
print(res)



from collections import Counter

n = int(input())
arr = [int(i) for i in input().split()]
cnt = Counter()
for i in arr:
    cnt[i] += 1
cur = Counter()
s = sum(arr)
d = 0
i = 0
for val in arr:
    n1 = cnt[val - 1] - cur[val - 1]
    n2 = cnt[val + 1] - cur[val + 1]
    n3 = cnt[val] - cur[val]
    d += s - (n - i) * val
    d -= n1 * (val - 1)
    d += n1 * val
    d -= n2 * (val + 1)
    d += n2 * val
    d -= n3 * val
    d += n3 * val
    i += 1
    s -= val
    cur[val] += 1
print(d)


from random import randint
from time import time
n = list(map(int, input().strip().split()))[0]
arr = list(map(int, input().strip().split()))

tik = time()
count = dict()
subsum = [0 for i in range(n + 1)]
for index in range(len(arr) - 1, -1, -1):
    if arr[index] in count:
        count[arr[index]] += 1
    else:
        count[arr[index]] = 1
    if index == len(arr) - 1:
        subsum[index] = arr[index]
    else:
        subsum[index] = arr[index] + subsum[index + 1]

answer = 0
for index, value in enumerate(arr):
    answer += subsum[index + 1] - ((len(arr) - index - 1) * arr[index])
    if value + 1 in count:
        answer -= count[value + 1]
    if value - 1 in count:
        answer += count[value - 1]
    count[value] -= 1
    if count[value] == 0:
        count.pop(value)
print(answer)

# -*- coding: utf-8 -*-
"""
Created on Tue Dec 12 20:33:55 2017

@author: savit
"""
dic={}
n=int(input())
sum1=0
a=list(map(int,input().split()))
for i in range(n-1,-1,-1):
    try:
        dic[a[i]]+=1
        
    except:
        dic[a[i]]=1
    sum1+=a[i]*(-n+1+2*i)
    
    try:
        #print(dic[a[i]+1],'dec',a[i])
        sum1-=dic[a[i]+1]
    except:
        pass
    try:
        #print(dic[a[i]-1],'inc',a[i])
        sum1+=dic[a[i]-1]
    except:
        pass
print(sum1)
        
    




n = int(input())
a = list(map(int, input().split(' ')))

d = {}
s = a[0]
ret = 0
d[a[0]] = 1
for i in range(1,n):
  ret += a[i]*i - s
  if a[i]-1 in d:
    ret -= d[a[i]-1]
  if a[i]+1 in d:
    ret += d[a[i]+1]
  s += a[i]
  if a[i] not in d:
    d[a[i]] = 0
  d[a[i]] += 1

print(ret)

from collections import defaultdict


n = input()
a = list(map(int, input().split()))
def solve(a):
    sum = a[0]
    res = 0
    size = 1
    counter = defaultdict(int)
    counter[a[0]] +=1

    for el in a[1:]:
        counter[el] += 1
        res = res - sum + size * el
        res = (res- counter[el-1]) + counter[el+1]
        size += 1
        sum += el
    return res
print(solve(a))

n = int(input())
cnt = {}
res = 0
s = 0
a = list(map(int, input().split()))
for i in range(n):
	x = a[i]
	s += x
	cnt[x] = cnt.get(x, 0) + 1
	res += x * (i + 1 - (cnt.get(x, 0) + cnt.get(x - 1, 0) + cnt.get(x + 1, 0))) - (s - (x * cnt.get(x, 0) + (x - 1) * cnt.get(x - 1, 0) + (x + 1) * cnt.get(x + 1, 0)))
print(res)

n =int(input())
a = list(map(int, input().split()))
res , sum = 0, a[0]
cnt = dict()
cnt[a[0]] = 1
for i in range(1, n):
    res += a[i] * i - sum
    sum += a[i]
    if (a[i] - 1) in cnt:
        res -= cnt[a[i] - 1]
    if (a[i] + 1) in cnt:
        res += cnt[a[i] + 1]
    if a[i] not in cnt:
        cnt[a[i]] = 1
    else:
        cnt[a[i]] += 1
print(res)

n = int(input())
cnt = dict()
s = 0
ans = 0
a = list(map(int, input().split()))
for i in range(0, n):
	ans += a[i] * i - s;
	ans -= cnt.get(a[i] - 1, 0)
	ans += cnt.get(a[i] + 1, 0)
	s += a[i]
	cnt[a[i]] = cnt.get(a[i], 0) + 1
print(ans)

N = 2 * 10**5 + 3
n = int(input())
A, cnt = list(map(int,input().split(' '))), {}

s, a = 0, 0

for i in range(n-1,-1,-1):
    a += s
    if (A[i]-1) in cnt:
        a += cnt[A[i]-1]
    if (A[i]+1) in cnt:
        a -= cnt[A[i]+1]
    a -= (n-(i+1))*A[i]
    s += A[i]
    if A[i] not in cnt:
        cnt[A[i]]=0
    cnt[A[i]] += 1

print(a)


n = int(input())
num = list(map(int, input().split()))

cnt = {}
cursum = 0
ans = 0

for i in range(n):
    ans += num[i] * i - cursum

    if (num[i] - 1) in cnt:
        ans -= cnt[num[i] - 1]
    if (num[i] + 1) in cnt:
        ans += cnt[num[i] + 1]

    cursum += num[i]
    if num[i] not in cnt:
        cnt[num[i]] = 0
    cnt[num[i]] += 1

print(ans)


from bisect import bisect


def main():
    n = int(input())
    an = [(i, int(s)) for i, s in enumerate(input().split())][:n]

    ans = sum(a * (-n + 1 + 2 * i) for i, a in an)

    group = {}
    for i, a in an:
        if a not in group:
            group[a] = []
        group[a].append(i)
    group = list(sorted(list(group.items()), key=lambda t: t[0]))
    # print(group)

    for i in range(len(group) - 1):
        if group[i][0] + 1 == group[i + 1][0]:
            idx_s1 = group[i][1]
            idx_s2 = group[i + 1][1]
            for idx in idx_s1:
                smaller = bisect(idx_s2, idx)
                larger = len(idx_s2) - smaller
                ans = ans - larger + smaller

    print(ans)


def __starting_point():
    main()

__starting_point()

m = {}
n = int(input())
l = list(map(int, input().split()))
Sum = 0
ans = 0

for i in range(n):
  ans += i * l[i] - Sum
  if m.__contains__(l[i] - 1) :
    ans -= m[l[i] - 1]
  if m.__contains__(l[i] + 1) :
    ans += m[l[i] + 1]
  if m.__contains__(l[i]) :
    m[l[i]] += 1
  else:
    m[l[i]] = 1
  Sum += l[i]

print(ans)




from collections import Counter

n = int(input())
l = list(map(int, input().split()))

ans = 0
s = 0

for i, a in enumerate(l):
    ans += a * i - s
    s += a

c = Counter()
for a in l:
    ans -= c[a-1]
    ans += c[a+1]
    c[a] += 1

print(ans)

n = int(input())
v = [int(x) for x in input().split()]
mp = {}
s = sum(v)
ans = 0
cnt = n

for i in range(n):
    if v[i] in mp:
        mp[v[i]] += 1
    else:
        mp[v[i]] = 1

for i in range(n):
    c = v[i]
    s -= c
    cnt -= 1
    ans += (s - (cnt*c))
    ans -= mp.get(c+1, 0)
    ans += mp.get(c-1, 0)
    mp[c] -= 1
    
print(ans)

cnt = {}
n = int(input())
s = 0
an = 0
a = list(map(int, input().split()))
for i in range(n):
    if a[i] not in list(cnt.keys()):
        cnt[a[i]] = 0
    if a[i] - 1 not in list(cnt.keys()):
        cnt[a[i] - 1] = 0
    if a[i] + 1 not in list(cnt.keys()):
        cnt[a[i] + 1] = 0
    s += a[i]
    cnt[a[i]] += 1
    num = i + 1 - cnt[a[i]] - cnt[a[i] - 1] - cnt[a[i] + 1]
    an += num * a[i] - (s - a[i] * cnt[a[i]] - (a[i] + 1) * cnt[a[i] + 1] - (a[i] - 1) * cnt[a[i] - 1])
print(an)


n = int(input())
dic = {}
ans = s = 0
k = input().split()
for i in range(n):
  a = int(k[i])

  if (a - 1) in dic:
    b = dic[a - 1]
  else:
    b = 0

  if a in dic:
    c = dic[a]
  else:
    c = 0
    dic.update({a:0})

  if (a + 1) in dic:
    d = dic[a + 1]
  else:
    d = 0      

  ans += a * (i - b - c - d) - s + b * (a - 1) + c*(a) + d * (a+1)  
  dic[a] += 1
  s += a

print(ans)