← 返回题目列表

AtCoder · agc044_b

B. 小丑

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

分数: 700 点

问题陈述

今晚,在您最喜欢的电影院里,他们正在放映电影《小丑》,所有座位都已满。电影院里有 N 行 N 每个座位,形成一个 N\times N 广场。我们用 1, 2,\dots, N 第一排观众(从左到右);与 N+1, \dots, 2N 第二排观众(从左到右);依此类推,直到最后一行,其观众由 N^2-N+1,\dots, N^2.

电影结束时,观众按照一定的顺序走出电影院: i第一个离开座位的观众是数字所表示的观众 P_i。观众 P_{i+1} 等待查看者 P_i 在离开座位之前就离开了电影院。 要退出电影院,观众必须从一个座位移动到另一个座位,直到退出座位广场(广场的任何一侧都是有效出口)。观众可以从一个座位移动到其中一个座位 4 相邻座位(同一行或同一列)。 离开电影院时,可能某个观众 x 穿过一个座位 目前 已被查看者占用 y;在这种情况下观众 y 会讨厌观众 x 永远。每个观众都会选择一种方式,尽量减少永远讨厌她的观众数量。

计算观看者对的数量 (x, y) 这样 y 会讨厌 x 永远。

约束

  • 2 \le N \le 500
  • 序列 P_1, P_2, \dots, P_{N^2} 是一个排列 \{1, 2, \dots, N^2\}.

输入

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

N
P_1 P_2 \cdots P_{N^2}

输出

If ans 是声明中描述的观看者对的数量,您应该在标准输出上打印

ans

示例输入 1

3
1 3 7 9 5 4 8 6 2

示例输出 1

1

电影结束前,观众在电影院内的安排如下:

1 2 3
4 5 6
7 8 9

前四名观众离开电影院(1, 3, 7, 9)可以不经过任何座位就离开电影院,因此不会被任何人讨厌。

那么,观众 5 必须经过观众所在的座位之一 2, 4, 6, 8 目前在离开电影院时就座;因此,至少其中一位观众会讨厌他。

最后剩下的观众可以离开电影院了(按顺序 4, 8, 6, 2)无需经过任何已占用的座位(实际上,他们可以完全不经过任何座位而离开电影院)。


示例输入 2

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

示例输出 2

3

示例输入 3

6
11 21 35 22 7 36 27 34 8 20 15 13 16 1 24 3 2 17 26 9 18 32 31 23 19 14 4 25 10 29 28 33 12 6 5 30

示例输出 3

11