Skiing
As you may know, Ukraine recently submitted a bid to host the 2022 Winter Olympic Games. To enhance the chances of winning this bid, we need to design the most ideal Olympic facilities. One such facility is a ski track that will be laid along a segment of a narrow plateau. This plateau consists of a series of gentle ascents and descents. If divided into sections of 1 km each, every section can be classified as either an ascent or a descent. For an optimal track for athletes, the number of ascent sections should equal the number of descent sections.
Given the sequence of ascents and descents of the plateau, determine the length of the longest possible track, i.e., a segment of the plateau that contains an equal number of ascents and descents.
Input Data
The first line provides a natural number n - the number of kilometer sections of the plateau. The second line contains n numbers that describe the terrain of the plateau. Each of these numbers is either a one (ascent) or a zero (descent). The plateau is not circular, meaning the first and last sections are not connected.
In approximately 40% of tests
2 ≤ n ≤ 100.In approximately 30% of tests 100 <
n ≤ 10000.In approximately 30% of tests 10000 <
n ≤ 1000000.
Output Data
Output the length in kilometers of the longest segment of the plateau that contains an equal number of ascents and descents. If no such segment exists, output the number 0.
Explanation of Examples
In the first example, the segment 1 1 0 0 of length 4 contains two ascents and two descents. The segment 1 0 0 1 also has this property. The given sequence does not have longer segments with an equal number of ascents and descents.
In the second example, the segment 0 1 of length 2 contains one ascent and one descent. There are no longer segments with an equal number of ascents and descents.
In the third example, no segment contains an equal number of ascents and descents.
In the fourth example, the longest segment containing an equal number of ascents and descents is the entire sequence.