Trò chơi những chiếc rương

Có $n$ chiếc rương đựng xu, đánh số từ $1$ đến $n$. Rương thứ $i$ ban đầu chứa $a_i$ đồng xu.

Trong mỗi lượt đi, người chơi chọn một số nguyên dương $x$ thoả mãn $2x+1\le n$, rồi lấy đúng một đồng xu từ mỗi rương mang số $x$, $2x$ và $2x+1$. Nếu một trong ba rương đó đã hết xu thì đơn giản là không lấy được đồng nào từ rương đó (lượt đi vẫn hợp lệ).

Trò chơi kết thúc khi tất cả các rương đều rỗng. Hãy tìm số lượt đi ít nhất để làm rỗng toàn bộ các rương. Nếu không tồn tại cách chơi nào làm rỗng hết các rương, in ra $-1$.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$ là số lượng rương.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$ là số xu ban đầu trong từng rương.

Dữ liệu ra

In ra một số nguyên duy nhất: số lượt đi ít nhất để làm rỗng tất cả các rương, hoặc $-1$ nếu không thể.

Ràng buộc

• $1\le n\le 100$
• $1\le a_i\le 1000$

Ví dụ