/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 700 点
問題文
映画「ジョーカー」が今夜放映されるとあり、あなたの行きつけの劇場はすでに満席です。この劇場には N 席の座席からなる列が N 列あり、これらの席が N\times N の正方形型に並んでいます。最前列の観客に左から 1, 2,\dots, N の番号を、前から 2 列目の観客に左から N+1, \dots, 2N の番号を付け、以降の観客にも同様に番号を付けます。最後列の観客の番号は、左から N^2-N+1,\dots, N^2 となります。
上映が終わると、観客は決まった順に劇場を出ます。i 番目に劇場を出るのは、番号 P_i の観客です。番号 P_{i+1} の観客は、番号 P_{i} の観客が劇場を出るまで待ってから移動します。劇場を出るには、席から席への移動を繰り返し、席からなる正方形型のエリアの外に出なければなりません (四辺のどこからでも出ることができます)。席から席への移動では、前後左右の 4 方向への移動が可能です。
番号 x の観客が、劇場を出る際に番号 y の別の観客が まだ座っている 席を通り抜けてしまうと、番号 x の観客は番号 y の観客に永遠に嫌われます。各観客は、自分を永遠に嫌う観客の数が最小となるように移動方法を選びます。
番号 x の観客が番号 y の観客に永遠に嫌われるような組 (x, y) の個数を求めてください。
制約
- 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}
出力
問題文で述べたような観客の組 (x, y) が ans 組存在するとして、標準出力に以下の形式で出力せよ。
ans
入力例 1
3 1 3 7 9 5 4 8 6 2
出力例 1
1
上映が終わる前の劇場内の観客の配置は以下の通りです。
1 2 3 4 5 6 7 8 9
劇場を出る最初の 4 人 (番号 1, 3, 7, 9 の観客) は席を通り抜けることなく劇場を出られるので、誰にも嫌われません。
その後、番号 5 の観客は、劇場を出る際に番号 2, 4, 6, 8 の観客が座る席のうちいずれかを通り抜けなければなりません。よって、番号 5 の観客は上記の観客のうち少なくとも一人に嫌われます。
最後に残った 4 人 (順に番号 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
Score : 700 points
Problem Statement
Tonight, in your favourite cinema they are giving the movie Joker and all seats are occupied. In the cinema there are N rows with N seats each, forming an N\times N square. We denote with 1, 2,\dots, N the viewers in the first row (from left to right); with N+1, \dots, 2N the viewers in the second row (from left to right); and so on until the last row, whose viewers are denoted by N^2-N+1,\dots, N^2.
At the end of the movie, the viewers go out of the cinema in a certain order: the i-th viewer leaving her seat is the one denoted by the number P_i. The viewer P_{i+1} waits until viewer P_i has left the cinema before leaving her seat. To exit from the cinema, a viewer must move from seat to seat until she exits the square of seats (any side of the square is a valid exit). A viewer can move from a seat to one of its 4 adjacent seats (same row or same column). While leaving the cinema, it might be that a certain viewer x goes through a seat currently occupied by viewer y; in that case viewer y will hate viewer x forever. Each viewer chooses the way that minimizes the number of viewers that will hate her forever.
Compute the number of pairs of viewers (x, y) such that y will hate x forever.
Constraints
- 2 \le N \le 500
- The sequence P_1, P_2, \dots, P_{N^2} is a permutation of \{1, 2, \dots, N^2\}.
Input
The input is given from Standard Input in the format
N
P_1 P_2 \cdots P_{N^2}
Output
If ans is the number of pairs of viewers described in the statement, you should print on Standard Output
ans
Sample Input 1
3 1 3 7 9 5 4 8 6 2
Sample Output 1
1
Before the end of the movie, the viewers are arranged in the cinema as follows:
1 2 3 4 5 6 7 8 9
The first four viewers leaving the cinema (1, 3, 7, 9) can leave the cinema without going through any seat, so they will not be hated by anybody.
Then, viewer 5 must go through one of the seats where viewers 2, 4, 6, 8 are currently seated while leaving the cinema; hence he will be hated by at least one of those viewers.
Finally the remaining viewers can leave the cinema (in the order 4, 8, 6, 2) without going through any occupied seat (actually, they can leave the cinema without going through any seat at all).
Sample Input 2
4 6 7 1 4 13 16 10 9 5 11 12 14 15 2 3 8
Sample Output 2
3
Sample Input 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
Sample Output 3
11