19454번 - Almost Longest Increasing Subsequence 다국어인터랙티브

문제

Suppose you are given a permutation $a$ of $n$ numbers from 1ドル$ to $n$. In a usual task you would have to find its {\it longest increasing subsequence}: indices $i_1,ドル $\ldots,ドル $i_k$ such that $i_1 < \ldots < i_k$ and $a_{i_1} < \ldots < a_{i_k},ドル where $k$ is maximum possible.

However, this time the task is different: the numbers are given online, so you must decide whether you take the number or not before you receive the next number. You also know that the input permutation is random, that is, selected uniformly at random from the set of all $n!$ possible permutations. Under these requirements it is impossible to surely find the longest increasing subsequence, but you have to just do good enough. Formally, let $k$ be the length of the longest increasing subsequence of the given permutation. Then, finding any increasing subsequence of length at least 0ドル.65k$ will suffice.

입력

출력

제한

프로토콜

First, interactor sends a single number $n$ ($n = 10^5$) which is the length of the permutation. Next, interactor sends $n$ numbers one by one, each on a separate line. After receiving each number you should print one integer to the standard output, which is 1ドル$ if you take the given number and 0ドル$ otherwise.

The sequence given is a permutation of 1ドル,ドル $\ldots,ドル $n$: all elements are distinct and each of then is from 1ドル$ to $n$.

Every number selected by participant (except for the first one) should be greater than the previous one.

In the sample case $n = 5$. Any solution which follows the output format passes this testcase.

힌트

The sample test is used only to illustrate the interaction format and is not included in the testset. Each test from the testset has $n = 10^5$.

In this problem, technically, a random permutation is an array of 1ドル,ドル $\ldots,ドル $n$ shuffled with some pseudo-random number generator.