문제

길이 의 순열 가 있다.

당신은 한 연산에서 다음과 같은 연산을 최대 회 할 수 있다.

• 인 과 을 고른다. 그 후 에서 부터 까지의 부분 수열의 순서를 반대로 뒤집는다. 이 연산의 비용은 이다.

예를 들어 에서 인 연산을 사용한다면, 가 된다.

연산을 최대 번만 하여 순열 를 오름차순으로 정렬하는 방법을 구해보자. 가능한 방법이 여러 가지라면, 사용한 연산의 비용의 합이 최소인 방법을 구해보자.

입력

첫째 줄에 이 주어진다.

둘째 줄에 가 공백으로 구분되어 주어진다.

출력

첫째 줄에 연산의 횟수 를 출력한다.

다음 개의 줄에 번째 연산 와 를 공백으로 구분하여 출력한다.

순열 를 최소한의 비용으로 정렬할 수 있는 방법이 여러 가지라면, 아무 방법이나 출력한다.

노트

길이 의 순열은 부터 까지의 수가 정확히 한 번 등장하는 수열을 말한다.

예를 들어, 와 는 순열이지만, 또는 은 순열이 아니다.

두 정수 와 에 대해, 는 를 로 나눈 나머지를 의미한다.