Domino cho biểu đồ Young

Cho một biểu đồ Young. Biểu đồ này là một biểu đồ cột gồm $n$ cột, cột thứ $i$ có chiều cao $a_i$ ô. Các cột được sắp xếp không tăng: $a_1\ge a_2\ge \dots \ge a_n\ge 1$. Mỗi ô là một hình vuông đơn vị, và các cột được đặt sát nhau, căn đáy về cùng một đường ngang.

Một quân domino là một hình chữ nhật kích thước $1\times 2$ hoặc $2\times 1$ (tức là phủ đúng hai ô kề nhau theo hàng ngang hoặc theo cột dọc).

Hãy tìm số quân domino nhiều nhất có thể đặt vào bên trong biểu đồ Young sao cho các quân domino không chồng lên nhau và mỗi quân nằm trọn trong biểu đồ.

Dữ liệu vào

• Dòng đầu chứa một 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$: chiều cao của các cột.

Dữ liệu ra

• In ra một số nguyên: số quân domino nhiều nhất có thể đặ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ụ