A choir director lines up n singers in a single row for a formation drill. Each singer has already been assigned a voice part: Alto or Soprano. The director wants to insert one imaginary divider somewhere along the row -- before the first singer, between any two adjacent singers, or after the last singer -- splitting the row into a left group and a right group (either group may be empty). For a divider placed at a given position, the formation's harmony score is defined as the number of Altos standing in the left group plus the number of Sopranos standing in the right group.
Find every divider position that achieves the maximum possible harmony score.
n, the number of singers.n space-separated integers, the i-th being 0 if singer i is an Alto or 1 if singer i is a Soprano, in row order.p from 0 to n inclusive, meaning the left group consists of the first p singers and the right group consists of the remaining n - p singers.1 <= n <= 10^50 or 1Example 1
Input
4 0 0 1 0
Expected
2 4
Explanation
Scores for divider positions 0..4 are 1, 2, 3, 2, 3 (e.g. at p=2 the left group [0,0] has 2 Altos and the right group [1,0] has 1 Soprano, giving 3). The maximum score is 3, achieved at positions 2 and 4.
Example 2
Input
3 0 0 0
Expected
3
Explanation
With every singer an Alto, the right group never contributes any Sopranos, so the score at position p is just p (the count of Altos moved into the left group). The score is maximized only at p=3, the largest possible position.
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 →