Phú ông ở làng AMK rất giàu có, ông có rất nhiều đất đai và nhiều khu rừng gỗ trồng lâu năm rất giá trị. Đặc biệt, ông có một khu rừng gỗ Xoan gồm \(n\) \((1 \leq n \leq 10^{5})\) cây được trồng thẳng hàng đang trong thời gian chờ khai thác. Phú ông đã nhờ chuyên gia về gỗ định giá trị cho từng cây. Cho dãy gồm \(n\) số \(a_{1},\ a_{2},\ a_{3},\ldots,\ a_{n}\) \((1 \leq a_{i} \leq 10^{6,1} \leq i \leq n)\) tương ứng là giá trị của cây gỗ thứ \(i\) trong khu rừng mà phú ông đã cho định giá. Phú ông có hai cô con gái, phú ông dự định cho hai cô con gái khai thác khu rừng này để làm vốn riêng. Vì yêu thương cô gái út của mình hơn nên phú ông muốn cô khai thác được tổng giá trị gỗ cao nhất. Ông đã đưa một cách khai thác như sau:

Bắt đầu, cô gái út sẽ chọn \(x\) \((1 \leq x \leq 3)\) cây gỗ liên tiếp đầu tiên để khai thác. Cô chị chọn x cây liên tiếp, tiếp theo (chú ý ở mỗi lượt chọn, cô út chọn \(x\) cây thì cô chị phải chọn \(x\) cây tiếp theo trừ khi số cây còn lại bé hơn \(x\), mỗi lượt chọn cô út có thể thay đổi giá trị \(x\) trong phạm vi đã cho, phải chọn theo thứ tự từ đầu khu rừng cho đến cuối khu rừng). Việc này cứ tiếp tục cho đến khi khai thác hết khu rừng.

Yêu cầu: Hãy đưa ra giá trị gỗ lớn nhất mà cô gái út khai thác được thỏa mãn yêu cầu bài toán.

Dữ liệu vào:

+ Dòng đầu tiên ghi số nguyên dương \(n\) là số cây gỗ Xoan trong khu rừng.

+ Dòng thứ hai ghi \(n\) số nguyên dương \(a_{1},\ a_{2},\ a_{3},..,\ a_{n}\) tương ứng là giá trị của từng cây gỗ trong khu rừng. Các số trên một dòng ghi cách nhau bởi một khoảng trắng.

Kết quả:

+ Ghi một số nguyên dương duy nhất là tổng giá trị gỗ khai thác lớn nhất của cô gái út.

Giải thích:

• Ở ví dụ 1, cô gái út chọn 3 cây liên tiếp đầu tiên trong lần chọn thứ nhất là 5, 4, 3. Do đó, cô chị cả không còn lựa chọn nào khác nên chọn 2. Khi đó, cô gái út thu được tổng số giá trị gỗ khai thác được lớn nhất là 5+4+3=12.

• Ở ví dụ 2, cô gái út chọn 2 cây đầu tiên là 10 và 8. Sau đó, cô cả chọn 7 và 11. Cuối cùng, cô gái út chọn 2 cây cuối cùng có giá trị 15 và 20. Do đó, số giá trị lớn nhất mà cô út thu được là 10+8+15+20=53.

Giới hạn:

• Có 30% số test ứng với 30% số điểm của bài có \(1 \leq n \leq 10^{2};1 \leq a_{i} \leq 1000\)

• Có 30% số test ứng với 30% số điểm của bài có \(1 \leq n \leq 10^{3};1 \leq a_{i} \leq 10^{5}\)

• Có 40% số test ứng với 40% số điểm của bài có \(1 \leq n \leq 10^{5};1 \leq a_{i} \leq 10^{6}\)