Hùng được cho một hình đa giác đều \(n\) (\(3 \leq n \leq 200000\)) cạnh. Lấy \(1\) cạnh bất kì mang chỉ số \(1\) và các cạnh tiếp theo được đánh số lần lượt là \(2, 3, \dots, n\) theo chiều kim đồng hồ. Trên cạnh thứ \(i\) của hình đa giác đều sẽ có \(a_i\) (\(1 \leq a_i \leq 2 \cdot 10^9\)) điểm. Các điểm này sẽ được đặt trên cạnh sao cho cạnh \(i\) được chia thành \(a_i + 1\) đoạn liên tiếp có độ dài bằng nhau.

Ví dụ, bạn có một đa giác đều có \(4\) cạnh với cạnh trên cùng mang chỉ số \(1\) và có mảng \(a = [2, 1, 3, 5]\) thì đa giác sẽ có dạng như sau.

Mỗi tam giác cô đơn bao gồm \(3\) điểm riêng biệt (không nhất thiết phải từ các cạnh khác nhau) là đỉnh của nó. Mỗi điểm chỉ có thể làm đỉnh của tối đa \(1\) tam giác cô đơn và tam giác ấy chỉ được gọi là cô đơn nếu không có bất kì tam giác nào giao với nó. Hãy đếm số lượng tam giác cô đơn lớn nhất có thể.

Input

• Dòng đầu tiên gồm \(1\) số nguyên dương \(n\) (\(3 \leq n \leq 200000\)) là số lượng cạnh của đa giác đều.
• Dòng thứ hai gồm \(n\) số nguyên dương \(a_i\) (\(1 \leq a_i \leq 2 \cdot 10^9\)).

Output

• \(1\) dòng duy nhất là kết quả của bài toán.

Example

4
3 1 4 6

4