Find Valid Starting Point in a Circular List

Given a circular list of integers, determine the starting index from which you can traverse the entire list such that the cumulative sum remains non-negative at every step. Formally, let the list be \(a_0, a_1, \dots, a_{n-1}\). You need to find the smallest index \(i\) such that for every \(0 \leq k < n\) the following holds:

\(\sum_{j=0}^{k} a_{(i+j) \% n} \ge 0\)

If no such index exists, output \(-1\). This problem involves a greedy strategy to simulate traversals and decide whether a candidate starting point is valid.

inputFormat

The input is given via standard input (stdin). The first line contains an integer \(n\), representing the number of elements in the list. The second line contains \(n\) space-separated integers representing the elements.

outputFormat

Output a single integer via standard output (stdout) representing the starting index if a valid one exists, otherwise output \(-1\).

## sample

5
1 -5 4 3 -2

2

</p>