세 번 뒤집기
시간 제한1초메모리 제한128 MB
세 번의 구간 뒤집기로 만들어진 1..N 배열이 주어질 때, 이를 원래 순서로 되돌리는 세 개의 구간 뒤집기(자명한 뒤집기 허용)를 구하는 문제입니다.
문제
1부터 N까지의 수가 차례대로 적힌 놀이판이 있다. 처음에는 왼쪽부터 1, 2, ..., N이 놓여 있다.
구간 [i, j]는 왼쪽에서 i번째 칸부터 j번째 칸까지의 모든 칸을 뜻한다. 항상 i <= j이다. 한 번의 조작으로 원하는 구간 하나를 골라 그 안의 순서를 완전히 뒤집을 수 있다.
N = 10인 처음 상태에서 구간 [3, 8]을 뒤집으면 놀이판은 다음과 같이 바뀐다.
이 상태에서 구간 [1, 5]를 뒤집고, 이어서 구간 [6, 9]를 뒤집으면 각각 다음 상태가 된다.
세 번의 구간 뒤집기를 거친 놀이판의 상태가 주어진다. 이 놀이판을 처음 상태인 1, 2, 3, ..., N으로 되돌리기 위해, 차례대로 뒤집을 세 구간을 구하라.
가능한 세 구간이 여러 가지라면 그중 아무거나 출력해도 된다. 구간 [i, i]를 뒤집는 것은 아무 변화도 만들지 않으며, 이런 구간도 사용할 수 있다.
입력
첫째 줄에 놀이판의 크기 N (5 <= N <= 1000)이 주어진다.
둘째 줄에 세 번의 구간 뒤집기 이후의 놀이판 상태를 나타내는 N개의 정수가 공백으로 구분되어 주어진다.
출력
입력된 놀이판을 처음 상태로 되돌리기 위해 차례대로 뒤집을 세 구간을 출력한다.
첫 세 줄에 각 구간 [i, j]의 i와 j를 공백으로 구분해 출력한다. 답은 항상 존재한다.