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:
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.
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 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.
31 2 3
001
91 2 3 2 5 4 3 8 5
001010111
91C 3f 4S 3h 88 6x 4W d1 8c
001010111
Name |
---|