Module

Cho mảng ~a~ gồm ~n~ số nguyên được đánh số từ ~1~ đến ~n~. Hàm ~f(x,y)~ được định nghĩa là số dư khi chia ~(x+y)~ cho ~10^8~.

Bạn hãy tính giá trị biểu thức:

$$\displaystyle \sum_{i=1}^{n-1}\sum_{j=i+1}^{n}f(a_i,a_j)$$

Input

• Dòng đầu tiên chứa số nguyên ~n~ ~(2 \le n \le 3 \times 10^5)~.
• Dòng thứ hai chứa ~n~ số nguyên mảng ~a~ ~(1 \le a_i < 10^8)~.

Output

• In ra giá trị biểu thức cần tính.

Examples

3
1 2 99999999

4

5
99999999 99999998 99999997 99999996 99999995

999999940

Notes

Trong ví dụ đầu tiên, các giá trị ~f(a_i,a_j)~ như sau:

• ~f(a_1,a_2)=3~
• ~f(a_1,a_3)=0~
• ~f(a_2,a_3)=1~