题目描述

考虑一个由(N)个二进制位组成的二进制字符串((b_1…b_N))。给定这样一个字符串，图1所示的矩阵是由该字符串的旋转版本构成的。

然后，按照字典序对矩阵的行进行排序，其中“(0)”排在“(1)”之前。你需要编写一个程序，给定已排序矩阵的最后一列，找到已排序矩阵的第一行。

举个例子，考虑字符串((00110))。已排序的矩阵是： [ \begin{matrix} 0 & 0 & 0 & 1 & 1 \ 0 & 0 & 1 & 1 & 0 \ 0 & 1 & 1 & 0 & 0 \ 1 & 0 & 0 & 0 & 1 \ 1 & 1 & 0 & 0 & 0 \ \end{matrix} ] 对应的最后一列是((1\ 0\ 0\ 1\ 0))。给定这最后一列，你的程序应该确定第一行，即((0\ 0\ 0\ 1\ 1))。

输入格式

第一行包含一个整数(N\leq3000)，表示二进制字符串中的二进制位数。第二行包含(N)个整数，是从下到上排列的最后一列的二进制位。

输出格式

第一行包含(N)个整数：从左到右排列的第一行的二进制位。

5
1 0 0 1 0

0 0 0 1 1

来源

2001年国际信息学奥林匹克竞赛（备用题目）