Page not loading? Try clicking here.
Placeholder

#3706

합이 0이 되는 연속구간 세기 1s 512MB

Problems

배열 A_1, A_2, A_3, … A_n이 주어졌을 때, 구간 [i,j]에 있어서(1≤i≤j≤n),

a_i + … +a_j 의 합이 0이 되는 모든 경우의 수를 구하는 프로그램을 작성하라

 

 

예를 들어 배열이 {5,-5,-7,7} 라면 답은 {5,-5} , {-7,7} , {5,-5,-7,7}의 3가지이다. 


Input

첫 줄에 배열의 원소 수인 n이 주어진다.(1≤n≤100,000)

 

다음 줄에 공백을 사이에 두고 n개의 배열의 원소들이 순서대로 주어진다. (-100≤a_i≤100) 


Output

한 줄에, 연속구간의 합이 0이 되는 모든 구간의 가짓수를 출력한다.​


Example #1

4

5 -5 -7 7
3

Example #2

8
1 0 0 1 -3 1 2 -1
8


Source

ohjtgood
You must sign in to write code.