통나무 정렬 2

문제의 배경

강물 위에 서로 다른 크기의 통나무가 많이 있다. 비버 하미드(Hamid)는 이 통나무들을 크기별로 재배치하려 한다. 하미드는 강둑을 따라 좌우로 이동하며 두 통나무 사이에서 서로의 크기를 비교하고 필요한 경우 두 통나무의 위치를 맞바꿀 것이다. 똑똑한 하미드는 통나무가 처음에 어떻게 놓여있는지에 상관없이 다음과 같은 방식으로 통나무를 분류할 수 있다는 것을 알고 있다.

1. 가장 왼쪽 통나무의 오른쪽 위치에서 시작한다.
2. 가장 오른쪽 통나무의 오른쪽 위치에 올 때까지 다음 작업을 반복한다.
* 왼쪽 통나무가 오른쪽 통나무보다 작은 경우: 오른쪽으로 한 칸 이동한다.
* 오른쪽 통나무가 왼쪽 통나무보다 작은 경우: 두 통나무의 위치를 교환하고, 시작위치가 아니라면 왼쪽으로 한 칸 이동한다.

 다음 그림은 위와 같은 방법으로 3개의 통나무를 크기별로 재배치하는 과정을 나타내고 있다. 이 과정에서 하미드는 총 4번 좌우로 이동하게 된다.

	오른쪽으로 이동		좌우 통나무 교환 후 왼쪽으로 이동		좌우 통나무 교환
	오른쪽으로 이동		오른쪽으로 이동 후 종료

통나무 위치를 크기순으로 정렬하기 위해 하미드가 이동해야 하는 횟수는 통나무들이 처음에 어떻게 놓여 있었는지에 따라 다르다. 최악의 경우 하미드는 4개의 통나무를 분류하기 위해 9번 이동해야 한다.

문제/도전

통나무의 갯수 n이 주어질 때, 통나무를 크기순으로 정렬하기 위해 하미드가 이동해야 하는 최소 이동 횟수와 최대 이동 횟수를 계산하는 프로그램을 작성해보자.

입력 설명

통나무의 갯수 n이 주어진다.(3 <= n <= 100000)

출력 설명

하미드의 최소 이동 횟수와 최대 이동 횟수를 공백을 기준으로 출력한다.

입력 예시

출력 예시