[CCO 2023] Line Town

Luogu

IDLGP10068

Time2000ms

Memory1024MB

DifficultyP7

2023CCO（加拿大）

线条小镇的 $N$ 个居民排成了一条线。最初，居民们从左到右沿着线的幸福值为 $h_{1}, h_{2}, \ldots, h_{N}$。你是线条小镇的镇长，你正在实施你的名为「社区、糖果和组织」（CCO）的计划。因此，你拥有了交换居民位置的权力。在一次交换中，你可以让两个相邻的居民交换他们在线中的位置。但是，这次交换会导致两个居民的幸福值取反。你想要知道是否能进行一些交换，使得居民的幸福值从左到右按非递减的顺序排列。如果可能，需要的最少交换次数是多少。 ## Input 第一行包含一个整数 $N$。第二行包含 $N$ 个整数 $h_{1}, \ldots, h_{N}$，表示从左到右的居民的幸福值。 ## Output 输出一行一个整数，表示最少的交换次数，如果任务不可能完成输出 $-1$。 [samples] ## Note **样例解释 1** 可以进行 3 次交换，如下所示： - 交换第 2 和第 3 个居民，幸福值变成了 $[-2,1,-7,-8,2,8]$。 - 交换第 4 和第 5 个居民，幸福值变成了 $[-2,1,-7,-2,8,8]$。 - 交换第 3 和第 4 个居民，幸福值变成了 $[-2,1,2,7,8,8]$。居民们现在按照要求的幸福值非递减的顺序排列了。没有比 3 次更少的交换次数可以得到非递减的排列。 **样例解释 2** 没有一系列的交换可以使居民按照幸福值非递减的顺序排列。对于所有的数据，有 $1\leq N\leq 5\times 10^5，-10^{9} \leq h_{i} \leq 10^{9}$。 - 额外限制 A：对于所有的 $i$，$\left|h_{i}\right| = 1$。 - 额外限制 B：对于所有的 $i$，$\left|h_{i}\right| \leq 1$。 - 额外限制 C：对于所有的 $i \neq j$，$\left|h_{i}\right| \neq\left|h_{j}\right|$。子任务编号| 分值| $N$ 的范围 |额外限制| |:-:|:-:|:-:|:-:| | 1 |12| $1 \leq N \leq 2000$ |A| |2 |12 |$1 \leq N \leq 5\times 10^5$|A| |3 |12| $1 \leq N \leq 2000$|B | |4 |16 |$1 \leq N \leq 5\times 10^5$|B| |5 |16 |$1 \leq N \leq 2000$| C| |6 |12 |$1 \leq N \leq 5\times 10^5$|C | |7|8 |$1 \leq N \leq 2000$ | | |8|12 |$1 \leq N \leq 5\times 10^5$ | |

Samples

Input #1

6
-2 7 -1 -8 2 8

Output #1

Input #2

4
1 -1 1 -1

Output #2

-1

API Response (JSON)

{
  "problem": {
    "name": "[CCO 2023] Line Town",
    "description": {
      "content": "线条小镇的 $N$ 个居民排成了一条线。最初，居民们从左到右沿着线的幸福值为 $h_{1}, h_{2}, \\ldots, h_{N}$。 你是线条小镇的镇长，你正在实施你的名为「社区、糖果和组织」（CCO）的计划。因此，你拥有了交换居民位置的权力。在一次交换中，你可以让两个相邻的居民交换他们在线中的位置。但是，这次交换会导致两个居民的幸福值取反。 你想要知道是否能进行一些交换，使得居民的幸福",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 1048576
    },
    "difficulty": {
      "LuoguStyle": "P7"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10068"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "线条小镇的 $N$ 个居民排成了一条线。最初，居民们从左到右沿着线的幸福值为 $h_{1}, h_{2}, \\ldots, h_{N}$。\n\n你是线条小镇的镇长，你正在实施你的名为「社区、糖果和组织」（CCO）的计划。因此，你拥有了交换居民位置的权力。在一次交换中，你可以让两个相邻的居民交换他们在线中的位置。但是，这次交换会导致两个居民的幸福值取反。\n\n你想要知道是否能进行一些交换，使得居民的幸福...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments