Problem Likelihood

Problem Statement

You are given a length $n$ string $s = s_1 s_2 ... s_n$ such that $s$ is a binary string (all characters are either $0$ or $1$). The string represents some information about the problems on your favourite problem solving site YeetCode.

For some character in $s$ there are two cases:

• if $s_i = 1$ then that means the $i^{th}$ YeetCode problem is a premium problem.
• if $s_i = 0$ then that means the $i^{th}$ YeetCode problem is not a premium problem (a non-premium problem).

Since you are poor, you do not have access to YeetCode premium, however, the people at YeetCode have coded it so that if you click the $\text{Random Problem}$ button, instead of only getting YeetCode non-premium problems, they put you on any random problem (uniformly distributed). When this happens, if you are on problem $i$, you will click the $\text{Next Problem}$ button and go to the next problem (problem $i + 1$) until you get to a non-premium problem. If you press the $\text{Next Problem}$ button and you are problem $n$, you will go to problem $1$.

You would like to determine the non-premium problem with which you have the most likelihood of ending on after going through this process. If there are multiple with the same highest probability, then choose the one with the smallest problem number.

Input Format

Your only line of input should contain a string of length $n$ representing $s$.

Output Format

Your only line of output should contain the problem you are most likely to end on,

Constraints

• $1 \leq n \leq 10^5$
• $s_i = 0$ or $s_i = 1$
• $s$ will contain at least one $0$

Sample Cases

1110110

4

1011011

2

01110001011101000111

1