Biến đổi

Cho dãy số nguyên không âm \(a_1, a_2, \dots, a_n\) (\(4 \le n \le 8\); \(a_i \le 10^9\)). Cần biến đổi dãy để tất cả các phần tử đều bằng \(0\). Mỗi bước được phép chọn \(4\) phần tử liên tiếp \(a, b, c, d\) biến đổi thành \(|a - b|, |b - c|, |c - d|, |d - a|\).

Ví dụ:
0 1 3 5 9
0 2 2 4 8 (1)
0 0 2 4 6 (2)
0 2 2 2 6 (3)
0 0 0 4 4 (4)
0 0 4 0 4 (5)
0 4 4 4 4 (6)
0 0 0 0 0 (7)

Yêu cầu: Hãy tính số phép biến đổi ít nhất cần thực hiện để tất cả các phần tử đều bằng \(0\).

Input

• Gồm một số dòng, mỗi dòng chứa một số nguyên là các phần tử của dãy \(a_1, a_2, \dots, a_n\).

Output

• Ghi số phép biến đổi ít nhất cần thực hiện để tất cả các phần tử đều bằng \(0\).

Example

0
1
3
5
9

7

Ràng buộc

• Có \(30\%\) số điểm tương ứng với \(n = 4\).
• Có \(30\%\) số điểm khác tương ứng với \(n \le 6\).
• \(40\%\) số điểm còn lại không có ràng buộc nào thêm.