Dọc theo một ống dẫn nước nóng, người ta lắp \(n\) cảm biến nhiệt độ cách đều nhau, được đánh số từ \(1\) tới \(n\). Cảm biến thứ \(i\) đang hiển thị nhiệt độ đo được là \(a_i\) (nhiệt độ). Nhiệt độ có xu hướng phụ thuộc vào vị trí trên đường ống, theo đó người ta tính toán được nhiệt độ trung bình về mặt lý thuyết của đoạn \([l; r]\) (\(1 \le l \le r \le n\)) là \(l + r\). Để kiểm chứng, họ cần đếm số lượng đoạn phù hợp với lý thuyết.

Yêu cầu: Hãy đếm số đoạn cảm biến liên tiếp mà nhiệt độ trung bình đo được bằng với nhiệt độ trung bình về mặt lý thuyết. Cụ thể cần đếm số đoạn \([l; r]\) (\(1 \le l \le r \le n\)) thỏa mãn:

Input

• Dòng đầu tiên chứa số nguyên dương \(n\) (\(1 \le n \le 3 \cdot 10^5\)).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) (\(|a_i| \le 10^9\)).

Output

• Một dòng chứa số nguyên duy nhất là số đoạn thỏa mãn.

Example

3
3 3 6

3

Scoring

• Subtask \(1\) (\(25\%\) số điểm): \(n \le 300\).
• Subtask \(2\) (\(25\%\) số điểm): \(n \le 3000\).
• Subtask \(3\) (\(50\%\) số điểm): Không có ràng buộc gì thêm.