Enhanced Fibonacci Words Substring Problem

This problem is an extended version of the problem Words from the third stage of the 16th Polish OI. It is designed for those who solved the original and want an extra challenge.

Define a function \( f \) acting on strings composed of the digits 0 and 1 as follows. For any string \( s \), the transformation \( f(s) \) is defined by replacing every digit independently and concurrently as follows:

• Replace each \( 0 \) with \( 1 \).
• Replace each \( 1 \) with \( 10 \).

For example, we have:

[ f(0)=1, \quad f(1)=10, \quad \text{and} \quad f(\varepsilon)=\varepsilon, ]

where \( \varepsilon \) denotes the empty string. Notice that \( f \) is an injection (one-to-one function).

For any nonnegative integer \( n \), let \( f^n \) denote the \( n \)-fold composition of \( f \) with itself, with the convention that \( f^0 \) is the identity function. In particular, we are interested in the sequence of strings of the form:

[ S_n = f^n(0), \quad n \ge 0. ]

This sequence begins as follows:

[ S_0=0, \quad S_1=1, \quad S_2=10, \quad S_3=101, \quad S_4=10110, \quad S_5=10110101, \dots ]

A string \( w \) is said to be a substring of a string \( s \) if it appears as a contiguous block in \( s \). Given a sequence of integers \( p_1,p_2,\dots,p_m \), define the pattern string \( P \) as the concatenation:

[ P = f^{p_1}(0) ; f^{p_2}(0) ; \cdots ; f^{p_m}(0). ]

Your task is to determine whether there exists an integer \( n \) such that \( P \) is a substring of \( f^n(0) \). If such an \( n \) exists, output the minimal \( n \) (note that \( n \) must be at least \( \max\{p_1,p_2,\dots,p_m\} \) because each \( f^{p_i}(0) \) is only defined in \( f^n(0) \) for \( n \ge p_i \)). Otherwise, output -1.

inputFormat

The input consists of two lines:

• The first line contains a single integer \( m \) representing the number of integers.
• The second line contains \( m \) space-separated nonnegative integers \( p_1, p_2, \dots, p_m \).

You may assume that all given \( p_i \)'s are small enough such that the corresponding strings \( f^{p_i}(0) \) have moderate lengths.

outputFormat

Output a single integer: the minimal \( n \) such that the concatenated string \( P = f^{p_1}(0)f^{p_2}(0)\cdots f^{p_m}(0) \) appears as a substring in \( f^n(0) \). If no such \( n \) exists within a reasonable bound, output -1.

sample

1
0

0

</p>