Minimum Swap

AtCoder

IDabc436_e

Time2000ms

Memory256MB

Difficulty—

You are given an integer sequence $P=(P _ 1,P _ 2,\ldots,P _ N)$ that is a permutation of $(1,2,\ldots,N)$. Here, it is guaranteed that $P$ is not equal to $(1,2,\ldots,N)$. You want to perform the following operation zero or more times to make $P$ match the sequence $(1,2,\ldots,N)$: * Choose a pair of integers $(i,j)$ satisfying $1\le i\lt j\le N$. Swap the values of $P _ i$ and $P _ j$. Let $K$ be the minimum number of operations required to make $P$ match the sequence $(1,2,\ldots,N)$. Find the number of operations that can be **the first operation** in a sequence of operations that makes $P$ match the sequence $(1,2,\ldots,N)$ in $K$ operations. Two operations are distinguished if and only if the chosen pairs of integers $(i,j)$ are different. ## Constraints * $2\le N\le3\times10 ^ 5$ * $1\le P _ i\le N\ (1\le i\le N)$ * $P _ i\ne P _ j\ (1\le i\lt j\le N)$ * There exists $1\le i\le N$ such that $i\ne P _ i$. * All input values are integers. ## Input The input is given from Standard Input in the following format: $N$ $P _ 1$ $P _ 2$ $\ldots$ $P _ N$ [samples]

Samples

Input #1

5
3 1 4 2 5

Output #1

6

For example, the goal can be achieved in three operations as follows:

*   Choose $(i,j)=(1,2)$. $P$ becomes $(1,3,4,2,5)$.
*   Choose $(i,j)=(2,4)$. $P$ becomes $(1,2,4,3,5)$.
*   Choose $(i,j)=(3,4)$. $P$ becomes $(1,2,3,4,5)$.

The goal cannot be achieved in two or fewer operations, so $K=3$.
As explained above, choosing $(1,2)$ for the first operation allows the goal to be achieved in three operations. Additionally, if one of $(1,3),(1,4),(2,3),(2,4),(3,4)$ is chosen for the first operation, then by performing the next two operations appropriately, $P$ can be made equal to $(1,2,3,4,5)$.
Therefore, print `6`.

Input #2

2
2 1

Output #2

Input #3

20
15 5 13 17 9 11 20 4 14 16 6 3 8 19 12 7 10 18 2 1

Output #3

API Response (JSON)

{
  "problem": {
    "name": "Minimum Swap",
    "description": {
      "content": "You are given an integer sequence $P=(P _ 1,P _ 2,\\ldots,P _ N)$ that is a permutation of $(1,2,\\ldots,N)$. Here, it is guaranteed that $P$ is not equal to $(1,2,\\ldots,N)$. You want to perform the fo",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc436_e"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given an integer sequence $P=(P _ 1,P _ 2,\\ldots,P _ N)$ that is a permutation of $(1,2,\\ldots,N)$. Here, it is guaranteed that $P$ is not equal to $(1,2,\\ldots,N)$.\nYou want to perform the fo...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments