D - Many Repunit Sum 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 400 点

問題文

i=1,2,\dots,N に対して、1 を A_i 個つなげた整数を B_i と表します。
より厳密には、B_i=\sum_{j=0}^{A_i-1}{10^j} と表します。
\sum_{i=1}^{N}{B_i} を求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq A_i \leq 2 \times 10^5
  • 入力される値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N  
A_1 A_2 \ldots A_N

出力

答えを 1 行で出力せよ。

入力例 1

4
3 3 3 3

出力例 1

444

B_1=B_2=B_3=B_4=111 なので、B_1+B_2+B_3+B_4=444 です。

入力例 2

3
30 10 20

出力例 2

111111111122222222223333333333

答えは非常に大きくなる可能性があります。

入力例 3

10
1 2 3 4 5 6 7 8 9 10

出力例 3

1234567900

Score : 400 points

Problem Statement

For i=1,2,\dots,N, let B_i denote the integer formed by concatenating A_i ones.
More formally, B_i=\sum_{j=0}^{A_i-1}{10^j}.
Find \sum_{i=1}^{N}{B_i}.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq A_i \leq 2 \times 10^5
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N  
A_1 A_2 \ldots A_N

Output

Output the answer in one line.

Sample Input 1

4
3 3 3 3

Sample Output 1

444

B_1=B_2=B_3=B_4=111, so B_1+B_2+B_3+B_4=444.

Sample Input 2

3
30 10 20

Sample Output 2

111111111122222222223333333333

The answer may be very large.

Sample Input 3

10
1 2 3 4 5 6 7 8 9 10

Sample Output 3

1234567900