소 W는 소 P로부터 받은 막대사탕 그림이 너무나도 막대사탕 같다고 느껴, 그에 대한 보답으로 덜 막대사탕 같은 색 리본을 선물했습니다.

소 W는 색 리본에 명암을 넣어 더욱 아름답게 만들고자 합니다.

$m$개의 칸으로 이루어진 색 리본에 대해, 색 리본을 길이 $m$의 명암 수열 $a$로 염색하는 난이도 $f(a)$를 다음과 같이 정의합니다.

• 초기 상태에서 색 리본의 모든 칸의 명암도는 $0$입니다.

• 당신은 여러 번의 조작을 수행할 수 있으며, 각 조작마다 다음을 수행해야 합니다.

  • 임의의 두 칸 사이의 구분선을 접는 선으로 하여 리본을 접습니다. 접기 조작은 여러 번 수행할 수도 있고, 수행하지 않을 수도 있습니다.
  • 한 위치를 선택하여 검은색 염료를 떨어뜨립니다. 염료는 위쪽에서부터 스며들어 아래로 흐르며, 경로에 있는 모든 칸의 명암도를 $1$ 증가시킵니다. 염료를 다 떨어뜨린 후 리본을 펼칩니다.

• $f(a)$는 모든 $a_i > 0$인 위치의 명암도가 $a_i$ 이상이 되고, 모든 $a_i = 0$인 위치의 명암도가 정확히 $0$이 되도록 만드는 데 필요한 최소 조작 횟수를 의미합니다.

이제 소 W는 길이 $n$인 색 리본과 길이 $n$인 후보 명암 수열 $b$를 가지고 있습니다. 그는 어떤 명암이 가장 보기 좋을지 아직 결정하지 못했기에, 모든 $b$의 부분 구간 $[l, r]$에 대하여 $r-l+1$개의 칸으로 구성된 색 리본을 염색하는 난이도의 합을 구하고자 합니다. 형식적으로 말하면, $\sum\limits_{1\le l\le r\le n}f(b[l,r])$을 구해야 합니다.

정답은 $2^{64}$로 나눈 나머지를 출력하십시오.

입력 형식

첫 번째 줄에 양의 정수 $n$이 주어집니다.

다음 줄에 $n$개의 음이 아닌 정수 $b_1, b_2, \dots, b_n$이 주어집니다.

출력 형식

정답을 $2^{64}$로 나눈 나머지를 음이 아닌 정수로 출력하십시오.

예제

입력 1

3
1 0 2

출력 1

9

입력 2

6
2 0 1 3 0 1

출력 2

51

입력 3

15
8 0 1 9 3 0 0 4 2 6 0 5 7 0 6

출력 3

993

데이터 범위

모든 데이터에 대하여: $1 \le n\le 10^6, 0\le b_i \le 10 ^ 9$입니다.