Shift and Reverse

AtCoder

IDarc132_b

Time2000ms

Memory256MB

Difficulty—

Given is a permutation $p_1,\dots,p_n$ of $1,\dots,n$. On this permutation, you can do the operations below any number of times in any order. * Reverse the entire permutation. That is, rearrange $p_1,p_2,\dots,p_n$ to $p_n,p_{n-1},\dots,p_1$. * Move the term at the beginning to the end. That is, rearrange $p_1,p_2,\dots,p_n$ to $p_2,\dots, p_n, p_1$. Find the minimum number of operations needed to sort the permutation in ascending order. In the given input, it is guaranteed that these operations can sort the permutation in ascending order. ## Constraints * $2 \leq n \leq 10^5$ * $p_1,\dots,p_n$ is a permutation of $1,\dots,n$. * The operations in Problem Statement can sort $p_1,\dots,p_n$ in ascending order. ## Input Input is given from Standard Input in the following format: $n$ $p_1$ $\dots$ $p_n$ [samples]

Samples

Input #1

3
1 3 2

Output #1

2

You can sort it in ascending order in two operations as follows.

1.  Move the term at the beginning to the end: now you have $3, 2, 1$.
2.  Reverse the whole permutation: now you have $1, 2, 3$.

You cannot sort it in less than two operations, so the answer is $2$.

Input #2

2
2 1

Output #2

1

Doing either operation once will sort it in ascending order.
You cannot sort it in less than one operation, so the answer is $1$.

Input #3

10
2 3 4 5 6 7 8 9 10 1

Output #3

3

You can sort it in ascending order in three operations as follows.

1.  Reverse the whole permutation: now you have $1,10,9,8,7,6,5,4,3,2$.
2.  Move the term at the beginning to the end: now you have $10,9,8,7,6,5,4,3,2,1$.
3.  Reverse the whole permutation: now you have $1,2,3,4,5,6,7,8,9,10$.

You cannot sort it in less than three operations, so the answer is $3$.

Input #4

12
1 2 3 4 5 6 7 8 9 10 11 12

Output #4

0

No operation is needed.

API Response (JSON)

{
  "problem": {
    "name": "Shift and Reverse",
    "description": {
      "content": "Given is a permutation $p_1,\\dots,p_n$ of $1,\\dots,n$. On this permutation, you can do the operations below any number of times in any order. *   Reverse the entire permutation. That is, rearrange $p",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "arc132_b"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Given is a permutation $p_1,\\dots,p_n$ of $1,\\dots,n$. On this permutation, you can do the operations below any number of times in any order.\n\n*   Reverse the entire permutation. That is, rearrange $p...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments