Domino trên biểu đồ Young

Cho một biểu đồ Young — tức một biểu đồ cột gồm $n$ cột có độ cao lần lượt $a_1,a_2,\dots ,a_n$, trong đó $a_1\ge a_2\ge \dots \ge a_n\ge 1$. Mỗi cột thứ $i$ gồm các ô vuông đơn vị xếp chồng từ đáy lên với tổng cộng $a_i$ ô.

Hãy tìm số lượng quân domino không chồng lên nhau lớn nhất có thể đặt vừa vào trong biểu đồ. Mỗi quân domino là một hình chữ nhật kích thước $1\times 2$ hoặc $2\times 1$ (đặt nằm ngang hoặc đặt thẳng đứng), và phải nằm hoàn toàn bên trong biểu đồ.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên $n$ — số cột của biểu đồ.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$ — độ cao của các cột.

Dữ liệu ra

• In ra một số nguyên — số lượng domino không chồng lên nhau lớn nhất.

Ràng buộc

• $1\le n\le 300000$
• $1\le a_i\le 300000$
• $a_i\ge a_{i+1}$ với mọi $1\le i<n$

Ví dụ