Almost Difference
题意翻译
- 定义函数
$$d(x,y)=\begin{cases}y-x,&\text{if }|x-y|>1\\0,&\text{if }|x-y|\le 1\end{cases}$$
- 给定长度为 $n$ 的序列 $a$，求
$$\sum_{i=1}^n\sum_{j=i+1}^n d(a_i,a_j)$$
- $1\le n\le 2\times 10^5$，$1\le a_i\le 10^9$。**答案可能会爆 `long long`**。
题目描述
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 $ .
输入输出格式
输入格式
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.
输出格式
Print one integer — the sum of $ d(a_{i},a_{j}) $ over all pairs $ (i,j) $ such that $ 1<=i<=j<=n $ .
输入输出样例
输入样例 #1
5
1 2 3 1 3
输出样例 #1
4
输入样例 #2
4
6 6 5 5
输出样例 #2
0
输入样例 #3
4
6 6 4 4
输出样例 #3
-8
说明
In the first example:
1. $ d(a_{1},a_{2})=0 $ ;
2. $ d(a_{1},a_{3})=2 $ ;
3. $ d(a_{1},a_{4})=0 $ ;
4. $ d(a_{1},a_{5})=2 $ ;
5. $ d(a_{2},a_{3})=0 $ ;
6. $ d(a_{2},a_{4})=0 $ ;
7. $ d(a_{2},a_{5})=0 $ ;
8. $ d(a_{3},a_{4})=-2 $ ;
9. $ d(a_{3},a_{5})=0 $ ;
10. $ d(a_{4},a_{5})=2 $ .