← 返回题目列表

AtCoder · math_and_algorithm_bg

073. 最大总和

中文机器翻译题面 查看原题

配点: 1000 点

問題文

N 整数 给出了 A_1, A_2, \cdots, A_N 减去 1 如何选择多个 2^N - 1 方法有很多。

对于这些,所有“所选整数的最大值”的总和是多少?回答 请打印除以 1000000007 后的余数。

制約

  • 1 \leq N \leq 300000
  • 1 \leq A_1 < A_2 < ... < A_N \leq 10^9
  • 所有输入均为整数

入力

输入是按以下格式从标准输入给出的。

N
A_1 A_2 \cdots A_N

出力

请打印答案。 到达


入力例 1

2
3 5

出力例 1

13

\{ 3 \}、\{ 5 \}、\{ 3, 5 \} 可以得到第 3 有多种选择方式,所以答案是 给出了 3+5+5=13 。