Given a integer value $n$, we generate a $n^2 \times n^2$ integer matrix $M$ in the following way.

1. Each ceil has value range $[1~n]$
2. In each row, the value is nondecreasing. E.g. $M[i, j] \leq M[i, j+1]$
3. In each column, the value is nondecreasing. E.g. $M[i, j] \leq M[i+1, j]$

For example the following is a example of $n=2$ & $4*4$ matrix.

1 1 1 2

1 1 1 2

2 2 2 2

2 2 2 2

We define the concept of turning point $(i,j)$ as

1. $M[i,j] = M[i, j+1] - 1$

2. $M[i,j] = M[i+1, j] - 1$

We can treat turning points as skyline points if you may. $M[n^2,n^2]$ is a special turning point.

For the above example, the turning points are $(2,3)$ and $(4,4)$.

We want to calculate the upper bound of total number of turning points, we denoted by $|P|$.

It is easy to proof that the upper bound size of set P is $O(n^3)$.

However, the real data shows that $|P|$ is always failing in the complexity of $n^2$ range.

Is there a way to proof that the upper bound of $|P|$ is $n^2$?