Bò của Farmer John muốn nhảy qua mặt trăng như trong bài đồng dao yêu thích. Tiếc là bò không thể nhảy.

Thầy phù thủy địa phương pha $P$ thuốc ($1 \le P \le 150{,}000$) để giúp chúng. Phải uống đúng thứ tự pha, nhưng có thể bỏ qua một số.

Mỗi thuốc có «sức mạnh» ($1 \le strength \le 500$) tăng khả năng nhảy. Uống ở bước lẻ làm tăng độ nhảy; bước chẵn làm giảm. Trước thuốc, khả năng nhảy dĩ nhiên là0.

Không uống thuốc hai lần. Sau khi bắt đầu, phải uống một thuốc mỗi bước từ thời gian1. Mỗi lượt có thể bỏ một hay nhiều thuốc.

Chọn thuốc để có cú nhảy cao nhất.

Dữ liệu vào

• Dòng $1$: số nguyên $P$.
• Các dòng $2..P+1$: mỗi dòng chứa số nguyên là sức mạnh thuốc. Dòng2 cho thuốc thứ nhất, dòng3 thứ hai, v.v.

Dữ liệu ra

• Dòng $1$: một số nguyên, mức nhảy lớn nhất có thể.

Ví dụ

Dữ liệu vào 1

8
7
2
1
8
4
3
5
6

Dữ liệu ra 1

17