Cyclic Message Notification

Uim works as a secretary in a company. He has n messages to notify his boss. Each message has an integer value that affects the boss's mood. Initially, the boss's mood is 0. After notifying a message with value \(d_i\), the boss's mood becomes the previous mood plus \(d_i\). However, if the boss’s mood becomes less than or equal to 0 after any notification, he will become furious and fire Uim.

The messages occur in a given order. Uim must report the messages in the order of their occurrence, but he is allowed to choose a cyclic starting point. In other words, for a given starting index \(k\) \((1 \leq k \leq n)\), he will report messages in the order \(k, k+1, \ldots, n, 1, 2, \ldots, k-1\).

Determine how many valid starting positions \(k\) exist such that when notifying the messages in that cyclic order, the boss's mood remains strictly positive after every message. Formally, let the messages be \(d_1, d_2, \ldots, d_n\) and define the prefix sums \(P(i)=\sum_{j=1}^{i}d_j\) with \(P(0)=0\). For a cyclic shift starting at index \(k\), the condition is that for every \(1 \leq i \leq n\), the mood

[ S_i = \begin{cases} P(i+k-1)-P(k-1) & \text{if } i+k-1 \le n,\[1mm] P(n)-P(k-1)+P(i+k-1-n) & \text{if } i+k-1 > n, \end{cases} ]

must satisfy (S_i > 0).

inputFormat

The first line contains an integer \(n\) (the number of messages). The second line contains \(n\) space-separated integers \(d_1, d_2, \ldots, d_n\) representing the values of the messages in the order of occurrence.

outputFormat

Output a single integer representing the number of valid starting positions \(k\) that allow Uim to notify the messages without making the boss angry.

sample

1
5

1