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.

If I correctly understand you, seems that it's a strightforward LIS problem, only you should reject tag cells with value $$$n$$$ for $$$x$$$ and $$$y$$$ coordinates (two or one tag cells). Let's denote LIS as $$$k$$$ then the answer is $$$2(n-1)-k$$$. LIS can be found in $$$O(nlogn)$$$.

Thanks very much. You give me idea. It just has some boundary condition which I handle them. for example each tag in column one and row one, doesn't help me. but idea is same. Thanks a lot.