While playing with the magnetic strips that came with his mini whiteboard, Gabe realized that the strips were made from several equal length bands of positive or negative magnets with no particular order. The strips are only magnetic on one side and Gabe enjoys folding them and trying to hold them together by matching positive bands with negative bands.
In order to make the strongest bond, Gabe would like to know the largest contiguous section on a strip that can be perfectly paired with another section on the same strip. Gabe will fold the strip exactly once to pair the bands. Folding can be done both in between bands and on the center of a band. More specifically, if the folding occurs in between band k and band k+1, after folding band k+1 will be paired with band k, band k+2 will be paired with band k-1, etc. If folding occurs on the center of band k, after folding band k+1 will be paired with band k-1, band k+2 will be paired with band k-2, etc.
The input consists of one line, a string of ‘+’ and ‘-’ characters denoting positive and negative bands on the magnetic strip. The length of this string is at least 1 and no more than 105.
On a line by itself, output the maximum length contiguous section that can be paired with another section on the same strip with a single fold. Note that maximum contiguous section can start on any band of the folded strip, i.e., it may not start at the beginning of the strip or at the folded spot.
Explanation for the second Sample Input/Output: we fold between band 4 and band 5 so, after folding (flipping) the right-hand side over the left-hand side, we’ll have: -+- ++-+ Explanation for the third Sample Input/Output: we fold between band 10 and band 11 so, after folding (flipping) the right-hand side over the left-hand side, we’ll have: +++---+++- +--+++---- Explanation for the last Sample Input/Output: we fold at the center of band 3 so, after folding (flipping) the right-hand side over the left-hand side, we’ll have: +-* -+* Note: we have used ‘*’ to indicate the folded band 3.