\(n\) circles are placed in a \(2D\) plane, with radii \(r_1, r_2, ..., r_n\) and centers \(O_1, O_2, ..., O_n\) such that these circles all intersect at a common point \(P\), no arrangement of the set \((O_j, O_i, P)\) is linear and \(r_i \neq r_j\), for all \(i, j\) satisfying \(0 \leq i \leq n\), \(0 \leq j \leq n\) and \(i \neq j\). Given the integers \(m_3, m_4, m_5, ..., m_{n-1}\), where \(m_k\) is the number of points in the plane where \(k\) circles intersect, find the number of sections these circles divide the whole plane into.

Example: If \(n = 9\) and \(m_3 = 0, m_4 = 2, m_5 = 0, m_6 = 1, m_7 = 0, m_8 = 0\), this means there are \(9\) circles all sharing a common point \(P\) and there are \(2\) distinct point such that \(4\) circles intersect and \(1\) point such that \(6\) circles intersect. At the other intersections, only \(2\) circles intersect.

Input

The first line contains the number \(n\) and the subsequent lines contain \(m_3, m_4, m_5, ..., m_{n-1}\).

• \(5 \leq n \leq 10^7\)
• \(0 \leq m_j\leq 10^5\)

Output

Print the total number of distinct sections formed by these circles on the plane.

Example 1

Input:

5
1
0

Output:

15

Example 2

Input:

10
0
2
0
1
0
0
0

Output:

40

Explanation

Input 1: Here's a way to construct \(5\) circles that all intersect at the point \(P\), and a point \(B\) where \(3\) circles intersect. If we count the number of sections in the entire plane, we can see there are \(15\) sections.

Input 2: Here's a way to construct \(10\) circles that all intersect at the point \(P\), a point \(B\), \(C\) where \(4\) circles intersect and a point \(D\) where \(6\) circles intersect. If we count the number of sections in the entire plane, we can see there are \(40\) sections.