합과 곱

Sarah와 Patricia는 어리고 재능이 뛰어난 자매다. 유치원에서 산수를 배운 뒤로, 두 사람은 낮이고 밤이고 어머니 Marguerite를 졸라대며 계산 연습을 하고 싶어 한다. Marguerite는 두 아이에게 산수 연습책을 사 주었는데, 이 책에는 n쪽의 페이지가 있고 각 페이지마다 양의 정수가 하나씩 적혀 있다. 그 정수들은 산수 계산을 연습하는 데 쓸 수 있다. Marguerite는 이 책이 한동안 두 아이를 붙잡아 두어 자신이 다른 집안일을 할 수 있기를 바란다.

Sarah와 Patricia는 자신이 계산한 답이 맞는지 알아야 하지만, Marguerite에게는 아이들의 답을 확인할 시간이 없다. 그래서 그녀는 적대적 유아 훈련이라는 기발한 방법을 떠올린다. Marguerite는 Sarah가 덧셈을 잘하고 Patricia가 곱셈에 재능이 있다는 것을 안다. 그래서 먼저 연속된 책 페이지의 구간을 하나 고르고(적어도 두 쪽), Sarah에게 그 페이지들에 적힌 정수의 합을 계산하게 하고 Patricia에게는 그 정수들의 곱을 계산하게 한다. 페이지를 잘 고르면 두 아이의 답이 같아지고, Marguerite는 그냥 Sarah와 Patricia가 서로 답을 비교하게 하면 된다!

Sarah와 Patricia는 같은 구간을 여러 번 연습하고 싶어 하지 않으므로, Marguerite는 유아 훈련에 쓸 페이지 구간을 몇 가지 서로 다른 방법으로 고를 수 있는지(그리고 언제 새 연습책을 사야 하는지) 알고 싶어 한다.

첫째 줄에 정수 n (2 ≤ n ≤ 2 · 105)이 하나 주어진다. 둘째 줄에는 산수 연습책의 페이지 순서대로 적힌 n개의 양의 정수가 주어진다. 이 정수 중 109보다 큰 것은 없다.

Sarah의 답과 Patricia의 답이 같아지도록 Marguerite가 적어도 두 쪽의 연속된 페이지로 이루어진 구간을 고르는 방법의 수를 정수 하나로 출력한다.