Server Time:

User's AC Ratio in this contest

16.7% (2/12)

Submission's AC Ratio in this contest

5.2% (3/58)

Description

農場有 $n$ 種史萊姆排成一列,每一種的數量分別為 $a_1, a_2, \cdots , a_n$

史萊姆可以好幾種混在一起進行繁殖,但繁殖的數量有特別的規則:
每種史萊姆各別會平均分成 $x$ 組,每種都會分成一樣多組,而且會分盡量多組,接著經過一段時間後就會生出 $x$ 隻混種史萊姆

你可以將該列任意連續種史萊姆圍起來,好讓他們進行繁殖
例如有 3 種史萊姆的數量分別為 $10, 4, 12$,則:

  • 這 3 種史萊姆能生出 $2$ 隻混種史萊姆
  • 前 2 種史萊姆能生出 $2$ 隻混種史萊姆
  • 後 2 種史萊姆能生出 $4$ 隻混種史萊姆

請問將所有連續種史萊姆進行繁殖後,總共能生出幾隻混種史萊姆?
例如 $a = (10, 4, 12)$,則一共能生出 $8 = 2 + 2 + 4$ 隻混種史萊姆

Input Format

第一列給定正整數 $n$ 表示有幾種史萊姆排成一列 $(1 \le n \le 5\cdot 10^5)$
第二列給 $n$ 個正整數 $a_i$ 表示從左到右此種史萊姆有幾隻 $(1 \le a_i \le 10^6)$

Output Format

輸出這些史萊姆一共能生出多少隻混種史萊姆

Sample Input 1

3
10 4 12

Sample Output 1

8

Sample Input 2

6
24 32 16 72 9 3

Sample Output 2

77

Sample Input 3

4
4 8 6 9

Sample Output 3

13

Sample Input 4

1
42

Sample Output 4

0

Hints

Problem Source

Subtasks

No. Testdata Range Score
1 0~44 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 2000 131072 65536 1
1 2000 131072 65536 1
2 2000 131072 65536 1
3 2000 131072 65536 1
4 2000 131072 65536 1
5 2000 131072 65536 1
6 2000 131072 65536 1
7 2000 131072 65536 1
8 2000 131072 65536 1
9 2000 131072 65536 1
10 2000 131072 65536 1
11 2000 131072 65536 1
12 2000 131072 65536 1
13 2000 131072 65536 1
14 2000 131072 65536 1
15 2000 131072 65536 1
16 2000 131072 65536 1
17 2000 131072 65536 1
18 2000 131072 65536 1
19 2000 131072 65536 1
20 2000 131072 65536 1
21 2000 131072 65536 1
22 2000 131072 65536 1
23 2000 131072 65536 1
24 2000 131072 65536 1
25 2000 131072 65536 1
26 2000 131072 65536 1
27 2000 131072 65536 1
28 2000 131072 65536 1
29 2000 131072 65536 1
30 2000 131072 65536 1
31 2000 131072 65536 1
32 2000 131072 65536 1
33 2000 131072 65536 1
34 2000 131072 65536 1
35 2000 131072 65536 1
36 2000 131072 65536 1
37 2000 131072 65536 1
38 2000 131072 65536 1
39 2000 131072 65536 1
40 2000 131072 65536 1
41 2000 131072 65536 1
42 2000 131072 65536 1
43 2000 131072 65536 1
44 2000 131072 65536 1