Farmer John은 아침에 목초지로 나가기 전에, 자신의 소들을 미리 정렬해 두려고 한다.
소는 편리하게도 1부터 N까지의 번호가 붙어 있으며, 모두 N마리 있다 (1 ≤ N ≤ 100).

현재 소들은 한 줄로 서 있고, 그 순서는 p_1, p_2, p_3, \dots, p_N이다. Farmer John은 소 p_1 바로 앞(줄의 맨 앞)에 서 있다.
Farmer John의 목표는 소들의 순서를 1, 2, 3, …, N으로 만드는 것이며, 이때 소 1이 Farmer John 바로 앞에 오도록 해야 한다.

하지만 오늘 소들이 너무 졸려 있어서, 어느 순간이든 Farmer John의 지시를 듣고 있는 소는 항상 Farmer John과 마주 보고 있는 맨 앞의 소 한 마리뿐이다.

한 번의 시간 단계에서 Farmer John은 이 소에게 다음과 같은 명령을 내릴 수 있다.

어떤 정수 k (1 ≤ k ≤ N-1)를 골라,
이 소에게 줄에서 뒤쪽으로 k칸 이동하라고 지시한다.

이때, 이 소가 지나쳐 가는 k마리의 소들은 앞으로 한 칸씩 전진하여 빈 자리를 메우고, 지시받은 소는 그들 뒤에 끼어들어간다.

예를 들어, N = 4이고 소들의 초기 순서가 다음과 같다고 하자.

FJ 앞: 4, 3, 2, 1

이때 Farmer John의 지시를 듣고 있는 소는 소 4뿐이다.
만약 그에게 "2칸 뒤로 가라"라고 지시하면, 이후 소들의 순서는 다음과 같이 된다.

FJ 앞: 3, 2, 4, 1

이제 Farmer John과 마주 보고 있는 소는 소 3이 되며, 두 번째 시간 단계에서 Farmer John은 소 3에게 또 다른 지시를 내릴 수 있다. 이런 식으로 계속 진행하여, 결국 소들의 순서를 정렬할 수 있다.

Farmer John은 소들을 가능한 한 빨리 정렬해서, 자기 아침 식사를 하러 농가로 돌아가고 싶어 한다.
Farmer John이 최적으로 행동할 때, 소들을 정렬하는 데 필요한 최소 시간 단계 수를 구하라.

#4103 upload 3 done 3 how_to_reg 2

Sleepy Cow Sorting timer 2s memory 512MB

#4103

Sleepy Cow Sorting 2s 512MB