Chessboard Tour 2

Time limit2sMemory limit512 MB

Summary

On an N by N board with distinct labels, find the fastest way to visit squares 1 through N^2 in order, choosing among knight, bishop, and rook moves and counting piece changes.

Level: Medium7 of 10
Topics: BFS, Graph, Shortest path, Implementation
Solved: No attempts yet

Problem

There is an N×N chessboard, and each square contains a distinct integer from 1 to N2. Jihak wants to play an interesting game on this board.

The pieces Jihak has are a knight, a bishop, and a rook. First, he places one piece on the square containing 1. Then he moves it in the order 1, 2, ..., N2.

First, he places one of the knight, bishop, or rook on 1. Then he moves the piece to the square containing 2. When moving from 1 to 2, he may visit squares containing other numbers. Then he moves it to the square containing 3, and so on, up to the square containing N2. Visiting the same square multiple times is allowed.

In one second, Jihak can either move the piece currently on the board or change it to a different piece.

Starting from 1, visiting 2, 3, ..., N2-1, and arriving at N2, find the minimum time required. If there are multiple ways to achieve the minimum time, minimize the number of piece changes.

Input

The first line gives the size of the chessboard, N (3 ≤ N ≤ 10).

The next N lines give the numbers written on the chessboard.

Output

On the first line, print the minimum time required to make the visits described in the problem, followed by the number of piece changes.

Examples4

Example 1
Input
```
3
1 9 3
8 6 7
4 2 5
```
Expected output
```
12 1
```
Example 2
Input
```
3
1 5 8
9 2 4
3 6 7
```
Expected output
```
12 1
```

Example 3

Input

Expected output

23 0

Example 4

Input

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

Expected output

38 2