Xét một dãy số nguyên không giảm \(s_1,\ldots,s_{n+1}\), nghĩa là \(s_i\le s_{i+1}\) với mọi \(1\le i\le n\). Dãy \(m_1,\ldots,m_n\) được xác định bởi \(m_i=\frac{s_i+s_{i+1}}{2}\) với \(1\le i\le n\) được gọi là dãy trung bình của dãy \(s_1,\ldots,s_{n+1}\).

Ví dụ, dãy trung bình của dãy \((1,2,2,4)\) là \((1.5,2,3)\). Các phần tử của dãy trung bình có thể không nguyên. Tuy nhiên, trong bài toán này, chỉ xét các dãy trung bình có tất cả phần tử là số nguyên.

Cho một dãy không giảm gồm \(n\) số nguyên \(m_1,\ldots,m_n\). Hãy tính số dãy không giảm gồm \(n+1\) số nguyên \(s_1,\ldots,s_{n+1}\) có dãy trung bình là dãy đã cho. Các phần tử của dãy \(s\) có thể là số âm.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu chứa số nguyên \(n\).
• \(n\) dòng tiếp theo chứa dãy \(m_1,\ldots,m_n\). Dòng thứ \(i+1\) chứa duy nhất số nguyên \(m_i\).

Dãy \(m\) được bảo đảm không giảm.

Dữ liệu ra

Ghi ra đầu ra chuẩn đúng một số nguyên: số dãy số nguyên không giảm có dãy trung bình là dãy đầu vào.

Ràng buộc

• \(2\le n\le 5\,000\,000\).
• \(0\le m_i\le 1\,000\,000\,000\) với mọi \(1\le i\le n\).
• \(m_i\le m_{i+1}\) với mọi \(1\le i<n\).

Phân nhóm

Trong \(50\%\) số bộ dữ liệu kiểm tra, \(n\le 1000\) và \(0\le m_i\le 20\,000\) với mọi \(1\le i\le n\).

Ví dụ

3
2
5
9

4

Nguồn

IOI 2005.