A supply-line dispatcher must divide a single-file column of checkpoints between two crews. The Vanguard crew always claims an unbroken prefix of the column, starting from the very first checkpoint; the Rearguard crew takes every checkpoint that remains. Each checkpoint is marked as either a reward checkpoint, worth one point to whichever crew passes through it, or a setback checkpoint, which costs its crew one point. Every checkpoint must go to exactly one crew, and each crew must be given at least one checkpoint.
Find the fewest checkpoints the Vanguard can be given (counted from the front of the column) so that the Vanguard's total points end up strictly greater than the Rearguard's total points. If no such split exists, report that it is impossible.
Line 1: an integer n, the number of checkpoints. Line 2: n space-separated integers, each either 0 or 1, listed in column order — 1 marks a reward checkpoint and 0 marks a setback checkpoint.
Print a single integer: the smallest number of checkpoints x (1 <= x <= n - 1) that must go to the Vanguard so that the Vanguard's total points strictly exceed the Rearguard's, or -1 if no split achieves this.
Example 1
Input
5 0 1 1 0 1
Expected
3
Explanation
Marks in order are [0,1,1,0,1] (setback, reward, reward, setback, reward). Giving the Vanguard the first x=1 checkpoint scores -1 for the Vanguard versus +1+1-1+1=2 for the Rearguard's remaining four; -1 is not greater than 2. At x=2 the Vanguard has -1+1=0 versus the Rearguard's 1-1+1=1; still not greater. At x=3 the Vanguard has -1+1+1=1 versus the Rearguard's last two, -1+1=0; 1 is strictly greater than 0, so x=3 is the first split that works, and it is the minimum.
Example 2
Input
4 0 1 0 1
Expected
-1
Explanation
Marks are [0,1,0,1]. At x=1 the Vanguard has -1 versus the Rearguard's 1-1+1=1 (not greater). At x=2 the Vanguard has -1+1=0 versus the Rearguard's -1+1=0 (a tie, not strictly greater). At x=3 the Vanguard has -1+1-1=-1 versus the Rearguard's 1 (not greater). No split lets the Vanguard finish strictly ahead, so the answer is -1.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →