8179번 - Words 2 다국어

The following task is a significantly harder version of task Words from the third stage of 16th Polish OI. It wasn't used in the contest itself, but is an extension for those who solved "Words" and want more. :-)

Let h be a function acting on strings composed of the digits 0 and 1. The function h transforms the string w by replacing (independently and concurrently) every digit 0 with 1 and every digit 1 with the string ,,10”. For example h(,,1001”)=,,101110”, h(,,”)=,,” (i.e. h assigns an empty string to the empty string). Note that h is an injection, or a one-to-one function. By h_k we denote the function h composed with itself k times. In particular, h⁰ is the identity function h⁰(w)=w.

We are interested in the strings of the form h^k(,,0”) for k=0,1,2,3,… This sequence begins with the following strings:

,,0”, ,,1”, ,,10”, ,,101”, ,,10110”, ,,10110101”.

We call the string x a substring of the string y if it occurs in y as a contiguous (i.e. one-block) subsequence. A sequence of integers k₁,k₂,…,k_n is given. Your task is to check whether a string of the form h^k₁(,,0”)⋅h^k₂(,,0”)⋅⋅⋅h^k_n(,,0”) is a substring of h^m(,,0”) for some m, and if it is, you shuold find minimal such m.

The first line of the standard input contains a single integer n, 1 ≤ n ≤ 1,000,000 . The second line of standard input holds n non-negative integers k₁,k₂,…,k_n (0 ≤ k_i ≤ 10⁹), separated by single spaces.

Your programme should print out t lines to the standard output, one for each test unit. Your programm should print to standard output minimal non-negative integer m, such that h^k₁(,,0”)⋅h^k₂(,,0”)⋅⋅⋅h^k_n(,,0”) is a substring of  h^m(,,0”), or NIE (no in Polish) if such m doesn't exist.

The string from the first test case is ,,110” - it is a substring of h⁴(,,0”)=,,10110”. In the second test unit there is a string ,,100”, which is not a substring of h^m(,,0”) for any m.