D. Balanced Array
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

Mr. Ham likes balance. He applies the concept of balance to integer arrays.

A balanced array is defined as an integer array $$$ a_1,a_2,\ldots a_l $$$ that satisfies the following condition:

  • There exists an integer $$$k$$$, such that $$$ 1\le k\le \frac {l-1} 2$$$.
  • $$$ a_i+a_{i+2k}=2a_{i+k} $$$ for each $$$ i $$$ in $$$ 1,2,\ldots l-2k $$$.

Given an array $$$ a_1,a_2,\ldots a_n $$$, Mr. Ham wants to determine whether $$$ a_{1\ldots i} $$$ is a balanced array for each $$$ i $$$ in $$$ 1,2,\ldots n $$$.

Please help Mr. Ham to solve the task.

Input

The first line contains an integer $$$ n $$$ ($$$ 1\le n\le 2\times 10^6 $$$), denoting the length of the array $$$ A $$$.

The second line contains $$$ n $$$ integers $$$ a_1,a_{2}\ldots a_{n} $$$ ($$$ 1\le a_i\le 2\times 10^8 $$$).

To minimize the size of the input file, $$$ a_i $$$ was encoded in base-62, where the characters $$$ \texttt{0}\ldots \texttt{9} \texttt{a}\ldots \texttt{z} \texttt{A}\ldots \texttt{Z}$$$ correspond to the numerical values $$$ 0\ldots 61 $$$ for each digit. For example, $$$\texttt{Aa0}$$$ represents $$$36\times 62^2+10\times 62+0=139004$$$.

Output

Output a binary string $$$ s_{1\ldots n} $$$, such that $$$ s_i=\texttt{1} $$$ if $$$ a_{1\ldots i} $$$ is balanced, $$$ s_i=\texttt{0} $$$ otherwise.

Examples
Input
3
1 2 3
Output
001
Input
9
1 2 3 2 5 4 3 8 5
Output
001010111
Input
9
1C 3f 4S 3h 88 6x 4W d1 8c
Output
001010111