Farmer John is attempting to sort his N cows (1 \leq N \leq 10^5), conveniently numbered 1 \dots N, before they head out to the pastures for breakfast.

Currently, the cows are standing in a line in the order p_1, p_2, p_3, \dots, p_N, and Farmer John is standing in front of cow p_1. He wants to reorder the cows so that they are in the order 1, 2, 3, \dots, N, with cow 1 next to Farmer John.

Today the cows are a bit sleepy, so at any point in time the only cow who is paying attention to Farmer John's instructions is the cow directly facing Farmer John. In one time step, he can instruct this cow to move k paces down the line, for any k between 1 and N-1 inclusive. The k cows whom she passes will amble forward, making room for her to insert herself in the line after them.

For example, suppose that N=4 and the cows start off in the following order:

 FJ: 4, 3, 2, 1

The only cow paying attention to FJ is cow $4$. If he instructs her to move $2$ paces down the line, the order will subsequently look like this:

 FJ: 3, 2, 4, 1

Now the only cow paying attention to FJ is cow 3, so in the second time step he may give cow 3 an instruction, and so forth until the cows are sorted.

Farmer John is eager to complete the sorting, so he can go back to the farmhouse for his own breakfast. Help him find a sequence of instructions that sorts the cows in the minimum number of time steps.

Problem credits: Dhruv Rohatgi

#4097 upload 2 done 2 how_to_reg 2 auto_awesome 스페셜 저지

Sleepy Cow Sorting timer 2s memory 512MB

#4097
스페셜 저지

Sleepy Cow Sorting 2s 512MB