String Theory

Given alternating runs of quote characters, find the largest k for which the whole string is a k-quotation.

Medium5Dynamic programmingStringIntervalsInterviewNo attempts yetTime limit2sMemory limit512 MB

Problem

Nested quotations are useful in literature with a layered narrative, and in programming languages as well. Using a different quotation mark at every nesting level makes the levels obvious, but there is another way. A kk-quotation marks the nesting level by repeating one single quote character, and it is defined as follows.

A 1-quotation is a string that starts with a quote character, ends with another quote character, and contains no quote character in between. This is the ordinary, unnested quotation. For example, 'this is a string' is a 1-quotation.

For k>1k > 1, a kk-quotation is a string that starts with kk quote characters, ends with another kk quote characters, and holds a nested string in between. The nested string is a non-empty sequence of (k1)(k-1)-quotations, and any number of non-quote characters may appear before them, between them, and after them. For example, ''All 'work' and no 'play''' is a 2-quotation.

You are given a description of a string. Find its largest possible nesting level.

Input

The first line contains an integer nn (1n1001 \le n \le 100). The second line contains nn integers a1,a2,,ana_1, a_2, \dots, a_n (1ai1001 \le a_i \le 100), which describe a string as follows. The string starts with a1a_1 quote characters, followed by a positive number of non-quote characters, followed by a2a_2 quote characters, followed by a positive number of non-quote characters, and so on, until the string ends with ana_n quote characters.

Output

Print the largest kk such that the described string is a kk-quotation. If no such kk exists, print no quotation instead.