题目描述

训练营新开放了一座机关展馆。展馆里一共有 n 个房间，必须按照第 1 个房间、第 2 个房间、……、第 n 个房间的顺序依次通过。

每个房间门口都有一排按钮。第 i 个房间有 a_i 个按钮，其中只有一个按钮能打开通往下一个房间的门。

如果按下了错误按钮，机关会立刻启动，把挑战者送回第 1 个房间门口，之前已经通过的房间也需要重新走一遍。

不过，挑战者会认真记录已经试过的按钮。也就是说：

• 如果某个房间的正确按钮已经被找到，以后再来到这个房间时，可以直接按正确按钮通过；
• 如果某个房间试过了一些错误按钮，下次再来到这个房间时，不会重复按这些错误按钮；
• 每次按按钮都算作一次操作。

现在假设运气最差：每个房间的正确按钮都是最后才被试出来的。

请你计算，在这种情况下，通过整个展馆一共需要按多少次按钮。

输入格式

第一行输入一个整数 n，表示房间数量。

第二行输入 n 个整数 a_1, a_2, ..., a_n，其中 a_i 表示第 i 个房间的按钮数量。

输出格式

输出一个整数，表示最差情况下通过整个展馆需要按按钮的总次数。

样例 1

2
1 1

2

样例 1 说明

两个房间都只有 1 个按钮，每个房间按一次就能通过，所以总共需要 2 次。

样例 2

2
2 2

5

样例 2 说明

在最差情况下，可以这样理解：

1. 第 1 个房间第一次按错，被送回起点；
2. 再来到第 1 个房间，按下剩下的正确按钮，通过；
3. 第 2 个房间第一次按错，被送回起点；
4. 第 1 个房间的正确按钮已经知道，按一次通过；
5. 第 2 个房间按下剩下的正确按钮，通过。

因此总共需要 5 次操作。

样例 3

5
2 1 3 2 1

16

样例 3 说明

依次计算每个房间带来的操作次数：

因此总操作次数为：

$2+1+7+5+1=16$。

数据范围

• 1 <= n <= 100
• 1 <= a_i <= 1000000000
• 保证答案不超过 10^18