Sleepy Cow Sorting (Bronze)#10330

Sleepy Cow Sorting (Bronze)

1 second
128 megabytes
Very easy

Farmer John is attempting to sort his cows, conveniently numbered from to , before they head out to the pastures for breakfast.

Currently, the cows are standing in a line in the order p_1, p_2, \ldots, 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, \ldots, n, with cow next to Farmer John.

The cows are a bit sleepy today, so at any moment, the only cow who is paying attention to Farmer John's instructions is the cow directly facing him. In one time step, he can instruct this cow to move positions down the line, for any integer in the range 1 \leq k \leq n-1. The cows whom she passes will move one step forward, making room for her to insert herself in the line after them.

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

 FJ: 4, 3, 2, 1 

The only cow paying attention to Farmer John is cow . If he instructs her to move positions down the line, the order will become:

 FJ: 3, 2, 4, 1 

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

Farmer John is eager to finish sorting so he can return to the farmhouse for his own breakfast. Help him find the minimum number of time steps required to sort the cows.

Input

The first line contains a single integer (1 \leq n \leq 100).

The second line contains integers p_1, p_2, \ldots, p_n indicating the starting order of the cows.

Output

Print a single integer: the minimum number of time steps required for all cows to be in sorted order, if Farmer John acts optimally.

Examples

Example 1

Loading
Loading