← 返回题目列表

AtCoder · abc268_e

H. 中餐厅(三星级版)

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

人 0, 人 1, \ldots和人 (N-1) 按逆时针顺序坐在转盘周围,间隔均匀。 菜品 p_i 在人的前面 i 在桌子上。
您可以执行以下操作 0 或多次:

  • 将转盘旋转一圈 N- 逆时针旋转一圈。 人面前的菜 i 旋转之前现在位于 Person 的前面 (i+1) \bmod N.

当你完成后,Person i 获得挫败感 k,其中 k 是满足 Dish 的最小整数 i 位于任一人的前面 (i-k) \bmod N 或人 (i+k) \bmod N.
求最小可能的挫败感总和 N 人。

什么是 a \bmod m? 对于整数 a 和一个正整数 m, a \bmod m 表示整数 x 之间 0 和 (m-1) (含)使得 (a-x) 是的倍数 m。 (可以证明这样 x 是唯一的。)

约束

  • 3 \leq N \leq 2 \times 10^5
  • 0 \leq p_i \leq N-1
  • p_i \neq p_j if i \neq j.
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N
p_0 \ldots p_{N-1}

输出

打印答案。


示例输入 1

4
1 2 0 3

示例输出 1

2

下图为一次操作后的表格。

在这里,他们的挫败感是 2 因为:

  • 人 0 感到沮丧 1 自从菜 0 在人的前面 3\ (=(0-1) \bmod 4);
  • 人 1 感到沮丧 0 自从菜 1 在人的前面 1\ (=(1+0) \bmod 4);
  • 人 2 感到沮丧 0 自从菜 2 在人的前面 2\ (=(2+0) \bmod 4);
  • 人 3 感到沮丧 1 自从菜 3 在人的前面 0\ (=(3+1) \bmod 4).

我们不能让他们的挫败感总和小于 2,所以答案是 2.


示例输入 2

3
0 1 2

示例输出 2

0

示例输入 3

10
3 9 6 1 7 2 8 0 5 4

示例输出 3

20