Hạo bị ám ảnh bởi các mẫu hoa văn. Ví dụ, bài tập về nhà yêu cầu anh xây một bức tường gạch sử dụng \(N\) viên gạch. Nhưng anh sẽ không bắt đầu xây cho đến khi hài lòng với bản phác thảo hai chiều của mình.

Trên bản phác thảo, mỗi viên gạch có thể được biểu diễn như một hình chữ nhật có chiều cao đơn vị và chiều rộng là \(d_i\). Anh chọn thứ tự các viên gạch trước và bắt đầu phác thảo từ hàng dưới cùng.

Ở hàng đầu tiên, anh sẽ đặt một số viên gạch từ trái sang phải. Ở hàng thứ hai, anh sẽ đặt gạch từ phải sang trái và viên gạch đầu tiên ở hàng thứ hai sẽ căn chỉnh với viên gạch cuối cùng ở hàng đầu tiên (các cạnh phải của chúng sẽ thẳng hàng). Tiếp theo, ở hàng thứ ba, anh sẽ đặt gạch lại từ trái sang phải. Viên gạch đầu tiên ở hàng thứ ba sẽ căn chỉnh với viên cuối cùng từ hàng thứ hai nhưng lần này là các cạnh trái. Anh tiếp tục quá trình này cho đến khi hết gạch. Anh có thể chọn xây tường với số hàng tùy ý.

Hạo sử dụng \(x_i\) măng siêu dính nên một viên gạch có thể được đặt trong tường mà không có viên gạch nào khác trực tiếp bên dưới. Độ đẹp của bức tường là số vị trí mà \(4\) viên gạch chạm nhau.

Với thứ tự các viên gạch cho trước và kích thước tương ứng của chúng, hãy tìm độ đẹp lớn nhất có thể của bức tường.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên \(N\) từ mô tả bài toán.
• Dòng thứ hai chứa \(N\) số nguyên \(d_i\) từ mô tả bài toán.

Dữ liệu ra

• In ra độ đẹp lớn nhất có thể của bất kỳ bức tường nào có thể xây được.

Chấm điểm

• Gọi \(M\) là chiều rộng của viên gạch lớn nhất. \(1 \le M \le 5,000\) sẽ đúng trừ khi có ghi chú khác.

Input 1

6
2 2 2 1 1 2

Output 1

2

Input 2

13
9 5 2 8 8 2 5 9 9 7 8 5 10

Output 2

5

Input 3

12
5 5 2 3 2 1 1 5 5 2 5 1

Output 3

4

Minh họa ví dụ 3