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 MBNested 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 k-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>1, a k-quotation is a string that starts with k quote characters, ends with another k quote characters, and holds a nested string in between. The nested string is a non-empty sequence of (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.
The first line contains an integer n (1≤n≤100). The second line contains n integers a1,a2,…,an (1≤ai≤100), which describe a string as follows. The string starts with a1 quote characters, followed by a positive number of non-quote characters, followed by a2 quote characters, followed by a positive number of non-quote characters, and so on, until the string ends with an quote characters.
Print the largest k such that the described string is a k-quotation. If no such k exists, print no quotation instead.