Bạn được cho một dãy số \(a\) gồm \(n\) số nguyên. Nhiệm vụ của bạn là tìm số cặp số \((i,j) \ 1 \leq i \leq j \leq n\) sao cho \(a_i + a_{i+1} + ... + a_j = 0\)

Input

• Dòng đầu tiên chứa số nguyên dương \(n \ (1 \leq n \leq 10^5)\) - là số phần tử của mảng.
• Dòng thứ hai chứa \(n\) số nguyên, số thứ \(i\) là \(a_i\) \(( \mid a_i\mid \leq 10^9)\)

Output

• Số lượng cặp số \((i,j)\) thõa mãn điều kiện trên

Example

4
-3 3 -4 4

3