34886번 - 인버전 과제 인터랙티브

문제

이 문제는 인터랙티브 문제입니다.

길이 $N$의 숨겨진 수열 $A_1, A_2, \ldots A_N$이 있다. $A_i$는 0ドル$ 또는 1ドル$이다. (1ドル \le i \le N$)

수열 $A$의 인버전을 $(1 \leq i < j \leq N)$를 만족하는 모든 정수 순서쌍 $(i,j)$에 대해 $A_i > A_j$를 만족하는 순서쌍의 개수로 정의한다.

건우는 전공 과목 수업 과제로 수열 $A$의 인버전을 0ドル$으로 만들어 제출해야 한다. 이미 과제 제출 기간이 3일 지난 건우는 아직도 귀찮기 때문에 당신이 건우를 위해 과제를 대신 해 주자.

당신은 $A$를 $A_l, A_{l+1}, \ldots, A_r$의 각 원소를 0ドル$이라면 1ドル$로, 1ドル$이라면 0ドル$으로 바꾸는 연산을 최대 $N$회 할 수 있다.

건우가 F를 받지 않도록 과제를 대신 해 도와주자.

입력

첫째 줄에 수열의 길이 $N$과 초기 수열 $A$의 인버전 $I$가 공백으로 구분되어 주어진다. (2ドル \leq N \leq 100;I \neq 0$)

출력

제한

인터랙션

이후 채점 시스템과의 인터랙션이 시작된다.

당신은 표준 출력에 다음 연산을 각 줄에 출력하는 것으로, 채점 시스템과 인터랙션할 수 있다. 각 토큰은 공백으로 구분하며, 각 연산의 끝에 개행문자를 출력하여야 한다.

당신은 정답을 구하기 위해 채점 시스템에게 다음과 같은 연산을 최대 $N$회 할 수 있다.

• $l$ $r$: $A_l, A_{l+1}, \ldots, A_r$을 뒤집는다.
  • $l \le i \le r$을 만족하는 모든 $i$에 대해 $A_i$가 0이라면 1로, $A_i$가 1ドル$이라면 0ドル$으로 바꾼다.
  • 연산이 $A$에 반영된 이후 다음 줄에 변경된 수열 $A$의 인버전의 개수 $I$가 입력으로 주어진다.
  • 만약 $I$가 0ドル$이라면 인버전을 0ドル$으로 만드는데 성공하였으므로 프로그램을 종료한다.
  • 1ドル \le l \le r \le N$

만약 연산이 잘못된 출력이거나 제한을 초과하였다면 당신은 -1을 다음 줄에 입력받으며 이 입력이 주어질 경우 프로그램을 즉시 종료해야 한다.

채점 시스템은 적응적이지 않다. 즉 초기에 $A$는 정해져 있으며 상호작용 도중에 $A$를 바꾸지 않는다.

각 연산 이후에는 표준 출력 버퍼를 비워야 한다.

각 언어별로 표준 출력 버퍼를 비우는 방법은 다음과 같다. 기타 언어의 경우, 언어의 레퍼런스 페이지를 참조하여라.

• C: fflush(stdout)
• C++: std::cout << std::flush
• Java, Kotlin: System.out.flush()
• Python: sys.stdout.flush()

노트