Mock Bronze B1 · "Flower Sorting"

← Back to mock contests · Original problem · Suggested time: 30–60 minutes

Problem

Bessie has N flowers arranged in a row, each with a positive height h_i. She wants the row sorted in non-decreasing order of height. In one operation she may pick any contiguous segment of flowers and reverse it.

Compute the minimum number of reversal operations Bessie needs to sort the row. If the row is already sorted, the answer is 0.

Input

Line 1: integer N (1 ≤ N ≤ 1000).
Line 2: N space-separated integers h_i (1 ≤ h_i ≤ 10⁹).

Output

A single integer: the minimum number of reversals required.

Samples

Input:
5
1 3 2 4 5

Output:
1

Reverse the segment [2..3] to turn 1 3 2 4 5 into 1 2 3 4 5.

Input:
4
4 3 2 1

Output:
1

A single full-array reversal sorts it.

Input:
6
3 1 2 6 4 5

Output:
2

Constraints

Time limit: 2 seconds
Memory: 256 MB
1 ≤ N ≤ 1000

Solution sketch (open after your 60-minute attempt)

Reveal idea

Count "breakpoints": positions i where h_i+1 < h_i in the sorted-value ordering. Each reversal can eliminate at most two breakpoints (the two endpoints of the reversed segment). So the answer is ⌈breakpoints / 2⌉, with a small exception when the row is already sorted (0 breakpoints → 0 reversals).

Implementation: compute the sorted target, walk through and count positions where the current array doesn't match the next-in-sorted-order. Divide by 2 (rounding up).

Reference complexity: O(N log N) (dominated by sorting).

Self-grading

Outcome	Score / 1000
Correct for all hand-checked cases incl. N=1, already-sorted, fully-reversed	1000
Correct on samples but you didn't verify edge cases	700
Brute force (try all 1- and 2-reversal combinations) — works at N ≤ 30 only	400
Didn't finish	0–200