Hi.
I'm sorry. I have a question but I couldn't solve it. it doesn't belong to codeforces. In this question, we have a n * n matrix and we want to go from (1,1) to (n,n). we only can move left, right, up, down. but there is a special tag on some cells. if we are in a cell and there is a special tag around us (I mean 8 side of a cell), we can move directly to that. Question guaranteed that each row and each cell contain exactly one tag.
We want to find minimum move to go from (1,1) to (n,n).
Question give information in special way. for example:

Input 1:

3  
1 2 3

Output 1:

2

Input 2:

4
2 3 1 4

Output 2:

4

in first row, n will given. in next row, n numbers will given. The i-th number mean which row in i-th column contain tag. range of n is 1 <= n <= 300000.

memory limit is 256Mb
Time limit is one second

I think solution is dynamic programming (dp). Because of memory limit , we can't construct a 2D array for out dynamic programming but because we always need just two last state, I only use 3 array for dp. It solves memory limit however time limit is one second and my dp algorithm which calculate all way, failed. it is a simple dp. it calculate 3 state (go down, right and diagonal for special tag). Is it possible to give me a better way?
I'm sorry for bad English. Thanks.