Cho dãy số nguyên \(A = (a_1, a_2, \ldots, a_n) (1 \le n \le 10^5;-10^6 \le a_i \le 10^6, \forall i \in [1, n]) \). Hãy tìm một đoạn dài nhất gồm các phần tử liên tiếp trong dãy \(A: (a_L, a_{L+1}, \ldots, a_H)\) sao cho tổng bằng \(0\).

Dữ liệu vào

Đọc từ file SZERO.INP:

• Dòng 1: Chứa số \(n\),
• Dòng 2: Chứa \(n\) số \(a_1, a_2, \ldots, a_n\) theo đúng thứ tự cách nhau ít nhất một dấu cách.

Kết quả

Ghi ra file SZERO.OUT:

• Một dòng duy nhất ghi hai số nguyên \(L, H\) cách nhau ít nhất một dấu cách.
• Đoạn \([L, H]\) là đoạn dài nhất có tổng bằng \(0\).

Ví dụ

SZERO.INP

9
2 7 5 -3 -2 4 -9 -2 1

SZERO.OUT

2 8

Ghi chú

Dữ liệu vào luôn được đảm bảo hợp lệ, tức là luôn tồn tại ít nhất một đoạn con liên tiếp có tổng bằng \(0\).

Ràng buộc

• Subtask 1: \(30\%\) số test, \(1 \le n \le 500\),
• Subtask 2: \(30\%\) số test, \(501 \le n \le 5000\),
• Subtask 3: \(20\%\) số test, \(5001 \le n \le 10^5\),
• Subtask 4: \(20\%\) số test, \(10^5 < n \le 10^6, -1 \le a[i] \le 1\).