Bob gửi cho Alice một dãy số nguyên gồm \(N\) phần tử: \(A_1,A_2,...,A_N\) đây là thông tin về một kho báu. Một đoạn con \((L,R)\) của dãy là một dãy gồm các phần tử liên tiếp \(A_L,A_{L+1},...,A_R\) với \(1\leq L < R \leq N\), đoạn con \((L,R)\) được gọi là chứa thông tin quan trọng nhất nếu:

• Phần tử đầu tiên bằng phần tử cuối cùng\((A_L = A_R)\)
• Tổng các phần tử của đoạn là lớn nhất có thể.

Yêu cầu

Hãy giúp Alice tìm đoạn con chứa thông tin quan trọng nhất.

Input

• Dòng thứ nhất chứa số nguyên dương \(N(N \leq 10^5)\).
• Dòng thứ hai chứa \(N\) số nguyên \(A_1,A_2,...,A_N)(|A_i| \leq 10^9, 1 \leq i \leq N)\)

Ràng buộc

• Subtask \(1(40\%\) số điểm\()\): \(N\leq 10^2\)
• Subtask \(2(30\%\) số điểm\()\): \(N \leq 10^3\)
• Subtask \(3(30\%\) số điểm\()\): \(N\leq 10^5\)

7
3 3 3 3 1 11 1

13