Chuỗi Ngoặc

Có một chuỗi ngoặc rất dài được nén lại dưới dạng một dãy gồm các số nguyên dương $c_1, c_2, ..., c_n$, trong đó $c_i$ là số lượng dấu ngoặc ( liên tiếp nếu $i$ là một số lẻ, hoặc là số lượng dấu ngoặc ) liên tiếp nếu $i$ là một số chẵn.

Ví dụ, với chuỗi ngoặc ((())())), dãy số tương ứng là $[3, 2, 1, 3]$.

Bạn cần tìm tổng số lượng chuỗi con liên tiếp (đoạn con) $[l, r]$ ($l ≤ r$) của chuỗi ngoặc ban đầu sao cho đoạn con này là một chuỗi ngoặc đúng.

Một chuỗi ngoặc được gọi là đúng nếu có thể chèn các ký tự + và 1 vào chuỗi này để thu được một biểu thức toán học hợp lệ. Ví dụ, các chuỗi (())(), () và (()(())) là chuỗi ngoặc đúng, trong khi )(, (() và (()))( thì không.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên đơn $n$ ($1 ≤ n ≤ 1000$), là kích thước của dãy nén.

Dòng thứ hai chứa một dãy các số nguyên $c_1, c_2, ..., c_n$ ($1 ≤ c_i ≤ 10^9$), biểu diễn dãy nén.

Kết quả

In ra một số nguyên duy nhất là tổng số lượng đoạn con của chuỗi ngoặc ban đầu tạo thành một chuỗi ngoặc đúng.

Có thể chứng minh rằng đáp án luôn nằm trong giới hạn của kiểu dữ liệu số nguyên có dấu 64 bit.

Chấm điểm

Subtask 1 (30 points). $n ≤ 100$

Subtask 2 (70 points). $1 ≤ n ≤ 1000$

Ví dụ

Input

2
2 2

Output

2

Ghi chú

Trong ví dụ, dãy nén biểu diễn chuỗi ngoặc (()). Chuỗi này chứa $2$ đoạn con là chuỗi ngoặc đúng:

• Đoạn con từ ký tự thứ $2$ đến thứ $3$: ()
• Đoạn con từ ký tự thứ $1$ đến thứ $4$: (())