Under construction

Still being built. Things may change

Moves You Need to Make

Time limit2sMemory limit512 MB

Summary
Given a permutation, find the fewest moves to sort it using adjacent swaps plus at most one swap of the first and last elements.
Level

Medium6 of 10

Topics
Array, Math, Implementation
Solved
No attempts yet

Problem

You are given a permutation.

A move is one of the following:

  1. Swap two adjacent elements.
  2. Swap the first and the last elements. Can be used at most once.

What is the minimum number of moves you need to make to sort the given permutation?

Input

The first line contains a single integer nn (1≤n≤3⋅1051 \leq n \leq 3 \cdot 10^5), the length of the permutation.

The second line contains nn integers aia_i (1≤ai≤n1 \leq a_i \leq n), the permutation itself.

Output

Output a single integer: the minimum number of moves you need to make to sort the given permutation.

Examples5

  1. Example 1

    Input
    1
1
    Expected output
    0

  2. Example 2

    Input
    2
1 2
    Expected output
    0

  3. Example 3

    Input
    3
3 2 1
    Expected output
    1

  4. Example 4

    Input
    4
4 2 1 3
    Expected output
    2

  5. Example 5

    Input
    5
4 1 5 3 2
    Expected output
    4