This page is still under construction.

Parts of this page are still being built. What you see may change.

String Theory

Interview

Time limit2sMemory limit512 MB

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

Medium5 of 10

Topics
Dynamic programming, String, Intervals
Solved
No attempts yet

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 (k−1)(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 (1≤n≤1001 \le n \le 100). The second line contains nn integers a1,a2,…,ana_1, a_2, \dots, a_n (1≤ai≤1001 \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.

Examples3

  1. Example 1

    Input
    5
    2 1 1 1 3
    
    Expected output
    2
    
  2. Example 2

    Input
    1
    22
    
    Expected output
    4
    
  3. Example 3

    Input
    1
    1
    
    Expected output
    no quotation