Subarray with Zero Sum

Problem statement

A campus shop records signed changes to a cash drawer throughout the day. The auditor wants to find whether any uninterrupted stretch of transactions leaves the balance exactly where it started, even if the drawer changed several times during that stretch. Your task Determine whether the array contains a nonempty contiguous subarray whose sum is zero. Important details Positive and negative transactions may cancel. A single zero is sufficient, but an empty selection is not. Transactions cannot be skipped or rearranged. Use a running sum and suitable lookup structure for an O(n) solution. Worked example For 4, -1, -3, 7, the first three transactions sum to zero. The audit therefore returns true, although none of these three values is individually zero.

Input format

The first line contains n. The next line contains n space-separated integers; for n = 0 this line may be empty.

Output format

Print true if the condition holds, otherwise false.

Constraints

1 <= n <= 100000; -1000000000 <= values <= 1000000000; use 64-bit sums.

Sample input

4
4 -1 -3 7

Sample output

true