Cho một mảng ~a~ gồm ~n~ phần tử ~a_1, a_2, \ldots, a_n~.

Yêu cầu

Tìm dãy đoạn con 3 phần tử liên tiếp có tổng nhỏ nhất trong các dãy đoạn con của mảng ~a~.

Dữ liệu vào

Nhập vào từ bàn phím gồm:

• Dòng đầu tiên chứa số nguyên dương ~n~ ~(n \le 10^5)~ là số phần tử mảng.
• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, \ldots, a_n~ ~(a_i \le 10^9)~.

  Kết quả

In ra một dòng duy nhất tổng đoạn con nhỏ nhất thỏa mãn yêu cầu đề bài.

Ví dụ

Dữ liệu vào

9
3 8 6 3 5 7 8 8 5

Kết quả in ra

14

Giải thích:

Đoạn con: ~[3;8;6]~, ~[8;6;3]~, ~[6;3;5]~, ~[3;5;7]~, ~[5;7;8]~, ~[7;8;8]~, ~[8;8;5]~, nên đoạn con có tổng nhỏ nhất là: ~14~.

Ràng buộc

• Có 40% số test thỏa mãn điều kiện ~1 \le n \le 10^2; 1 \le a_i \le 10^2~.
• Có 40% số test thỏa mãn điều kiện ~10^2 < n \le 10^4; 10^2 < a_i \le 10^5~.
• Có 20% số test thỏa mãn điều kiện ~10^4 < n \le 10^5; 10^5 < a_i \le 10^9~.