Đề bài

Cho dãy ~ n ~ số nguyên nằm trên vòng tròn theo chiều kim đồng hồ. Hãy xác định dãy con liên tiếp (có ít nhất một phần tử) có tổng các phần tử là nhỏ nhất.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên ~ n ~ ~(n \leq 100)~: số lượng phần tử trong dãy.
• Dòng thứ hai chứa ~ n ~ số nguyên ~ a_1, a_2, \dots, a_n ~ với ~ |a_i| \leq 10^9 ~.

Dữ liệu ra

• In ra một số nguyên duy nhất là tổng nhỏ nhất của dãy con liên tiếp tìm được.

Ví dụ

Dữ liệu vào:

4
2 -3 5 -4

Dữ liệu ra:

-5

Giải thích

• Dãy số trên vòng tròn có thể xem như nối các phần tử liên tiếp lại, với phần tử cuối nối liền phần tử đầu.
• Các dãy con hợp lệ có tổng nhỏ nhất gồm:
  
  • ~[-4 2 -3]~: tổng ~ -5 ~.
• Kết quả là ~ -5 ~.