这是一个交互式问题。

假设给定一个由 $1$ 到 $n$ 的数字组成的排列 $a$。在通常的任务中，你需要找到它的最长上升子序列：即满足 $i_1 < \dots < i_k$ 且 $a_{i_1} < \dots < a_{i_k}$ 的下标序列 $i_1, \dots, i_k$，其中 $k$ 是可能的最大值。

然而，这次的任务有所不同：数字是在线给出的，因此你必须在接收下一个数字之前决定是否选取当前数字。你还知道输入的排列是随机的，即从所有 $n!$ 种可能的排列中均匀随机选择。在这些要求下，无法确定地找到最长上升子序列，但你只需要做得足够好即可。形式化地说，令 $k$ 为给定排列的最长上升子序列的长度，那么找到任意长度至少为 $0.65k$ 的上升子序列即满足要求。

交互

首先，交互器发送一个数字 $n$ ($n = 10^5$)，表示排列的长度。接下来，交互器逐个发送 $n$ 个数字，每个数字占一行。在接收到每个数字后，你应该向标准输出打印一个整数，如果你选取该数字则输出 $1$，否则输出 $0$。

给定的序列是 $1, \dots, n$ 的一个排列：所有元素互不相同，且每个元素都在 $1$ 到 $n$ 之间。

参与者选择的每个数字（第一个除外）都必须大于前一个被选中的数字。

在样例中 $n = 5$。任何遵循输出格式的解法都能通过该测试用例。

样例

输入 1

5
2
1
5
4
3

输出 1

1
0
1
0
0

说明

样例测试仅用于说明交互格式，不包含在测试集中。测试集中的每个测试用例均有 $n = 10^5$。

在本题中，从技术上讲，随机排列是指将 $1, \dots, n$ 通过某种伪随机数生成器进行洗牌得到的数组。