400 dollars obtained

Count increasing 2-paths which have one edge in each direction.

Answer is $\dfrac{n^4-n^2}{12}.$ Construction is to number complete diagonals in order, such as in the following:

To bound this, consider triples of cells such that exactly two are aligned on each axis (basically an L shape of any size and orientation). Call such a triple an elbow if the corner cell of the triple is either larger than or smaller than both the other two cells. We will bound the number of elbows. For each cell $c$ in the grid, let $f(c)$ denote the number of cells in its column smaller than it, and $g(c)$ be the number of cells in its row smaller than it. Then the number of elbows with $c$ as the corner cell is exactly $$f(c)g(c)+(n-1-f(c))(n-1-g(c)).$$ By considering each column, it is clear that the number of times $f(c)=k$ for $0\le k\le n-1$ is exactly $n$ times. (Consider the relative ordering of numbers within each column.) The same is true for $g(c).$ So the total number of elbows over all $c$ is \begin{align*} &\sum_c f(c)g(c)+(n-1)^2-(n-1)(f(c)+g(c))+f(c)g(c)\\ &= n^2(n-1)^2-(n-1)\sum_c (f(c)+g(c)) +2\sum_c f(c)g(c)\\ \end{align*} By rearrangement inequality, this value is maximized when $f(c)=g(c)$ for all $c.$ (This is why equality holds in our maximum construction.) Thus the maximum number of elbows is exactly \begin{align*} &n^2(n-1)^2-(n-1)\cdot(n^2(n-1))+n\cdot\frac{(n-1)n(2n-1)}3\\ &=\frac{n^2(n-1)(2n-1)}3\\ \end{align*} Now consider the number of rectangles asked for in the problem, and let this be $x.$ Then there are $\binom{n}2^2-x$ nondesired rectangles. Each of the desired rectangles contains exactly 4 elbows, while the nondesired rectangles contain exactly 2 elbows. Thus, $$4x+2\left(\binom{n}2^2-x\right)\le\frac{n^2(n-1)(2n-1)}3.$$ So $$x\le\frac{n^2(n-1)(2n-1)}6-\frac{n^2(n-1)^2}4=\frac{n^4-n^2}{12},$$as desired. $\blacksquare$

@above what a great solution!

Call a rectangle $\emph{good}$ if its two smallest integers are on opposite vertices. Let $M$ be the number of ordered triples of distinct squares $(Q_1,P,Q_2)$ such that $P$ and $Q_1$ are in the same row, $P$ and $Q_2$ are in the same column, the the number in $P$ is less than the numbers in $Q_1$ and $Q_2.$ For each good rectangle, exactly $2$ of its $4$ sets of three consecutive vertices correspond to valid triples. For each non-good rectangle, exactly $1$ does. Thus, $M=2N+\binom{n}{2}^2-N=N+\binom{n}{2}^2.$ On the other hand, the number of triples with a given $P$ is equal to the product of the row "ranking" of $P$ (i.e. the number of squares in its row with greater numbers) and the column "ranking" of $P$ (i.e. the number of squares in its column with greater numbers). Also, exactly $n$ squares have row ranking $i$ for any $0\leq i\leq n-1$, and exactly $n$ squares have column ranking $i$ for any $0\leq i\leq n-1.$ So by the rearrangement inequality, $$M\leq n\cdot 0^2+n\cdot 1^2+\dots+n\cdot (n-1)^2=\frac{n^2(n-1)(2n-1)}{6}.$$ Thus, $$N\leq M-\binom{n}{2}^2=\frac{n^2(n^2-1)}{12}.$$This is constructed by just labeling the diagonals in order.

after many hours of thinking about this problem I have concluded it is absolutely trivial The answer is $\frac{n^2(n^2-1)}{12}$. We minimize the number of rectangles that don't work instead. Note that each of these rectangles has exactly two vertices whose values are between their two neighboring vertices', while working rectangles have none. Thus, between any pair of cells sharing a row or column draw an arrow from the smaller to the larger; the number of directed paths $v_1 \to v \to v_2$ is twice the number of bad rectangles. In each row (resp. column) there's a vertex with "row-indegree" $i$ for all $0 \leq i \leq n-1$, and "row-outdegree" is equal to $n-1$ minus "row-indegree". Let $x_{ij}$ and $y_{ij}$ denote the row and column indegrees of cell $(i,j)$ for $1 \leq i,j \leq n$, so we have $\{x_{ik}\}_k=\{y_{kj}\}_k=\{0,\ldots,n-1\}$ and the quantity we're counting is $\sum_{1 \leq i,j \leq n} x_{ij}y_{ij}+(n-1-x_{ij})(n-1-y_{ij})=\sum_{1 \leq i,j \leq n} (n-1)^2-(n-1)(x_{ij}+y_{ij})+2x_{ij}y_{ij}$. Maximizing this clearly amounts to maximizing $2\sum x_{ij}y_{ij}$ (actually these expressions are equal lmao), which by rearrangement is $n\sum_{i=0}^{n-1} i(n-1-i)=\frac{n^2(n-1)(n-2)}{12}$ (achieved when $x_{ij}+y_{ij}=n-1$), so the quantity we're counting is at least $\frac{n^2(n-1)(n-2)}{6}$ and the number of good rectangles is at most $\frac{n^2(n-1)^2}{4}$ minus this or $\frac{n^2(n^2-1)}{12}$ as desired. For a construction color by diagonal; it's easy to see that this fits the rearrangement equality case

Very Nice. We claim that the answer is $n^2(n^2-1)/12$ achieved by diagonal type construction; that is, $1,2, \cdots n$ in center diagonal $n+1,n+2 \cdots$ in the following diagonal and continue in similar fashion. Let $f(i,j)$ denote the number of cells in row $j$ less than $C_{i,j}$ and similarly we define $g(i,j)$ for columns. Define $L$ to be three cells $C_{i,j},C_{k,j},C_{i,k}$ such that $C_{i,k},C_{i,j},C_{k,j}$ is neither in increasing or decreasing order, we count the number of $L$ in the grid, which evidently equal to $\sum f(i,j)g(i,j)+(n-1-f(i,j))(n-1-g(i,j))$, considering each row/column we know that the number of times $f(i,j)$ appears in $n$, and so the sum becomes $n^2(n-1)^2-(n-1)\sum f(i,j)+g(i,j) + \quad + \sum 2f(i,j)g(i,j)$ which is clearly maximized when all $f(i,j)=g(i,j)$ which gives the same answer as desired.

In each row and column, draw an arrow for each pair of squares in the row and and column pointing from large to small. Let the row indegree and the column indegree be the number of arrows pointing to that square in that row and column, respectively. Note that for every rectangle that doesn't work there are exactly $2$ paths in arrows from one corner to another. For a rectangle that works there are obviously none. Therefore we try to minimize the number of paths of length $2$ on the arrows. Note that in each row each indegree from $0$ to $n-1$ inclusive must be assigned to a square. Same for columns. Let the row indegree and column indegree for an arbitrary square be $a_i,b_i,$ respectively. Then we are finding the minimum $a_i(n-1-b_i)+b_i(n-1-a_i)=(a_i+b_i)(n-1)-2a_ib_i.$ Summing over all possible $a_i,b_i$ for all rows is obviously $2\cdot n\cdot \frac{n(n-1)}{2},$ so the first term is $n^2(n-1)^2.$ As we want to maximize the sum of all $a_ib_i,$ by the rearrangement inequality we have that the maximum is when all $a_i=b_i.$ As this is $n$ times the sum of squares from $1$ to $(n-1)^2,$ which is $\frac{(n^2(n-1)(2n-1))}{6}.$ Therefore by subtracting $\frac 12(n^2(n-1)^2-\frac{(n^2(n-1)(2n-1))}{3})$ from $\frac{n^2(n-1)^2}{4},$ our answer is $$\boxed{\frac{n^2(n-1)(n+1)}{12}}.$$Construction is just having the smallest $n$ numbers be on the diagonal from lower left to top right, the next $n$ numbers being on the smaller diagonal to the immediate left of that main diagonal and the lower right corner, the next $n$ numbers being on the next diagonal to the immediate left of the previous diagonal and the remaining numbers not fitting in that diagonal on the diagonal on the immediate left of that lower right corner, and so on$.\blacksquare$

I claim the answer is $\frac{n^4-n^2}{12}$, for a cell $k$ let $f(k)$ denote the coloumn indegree and $g(k)$ denote the row indegree, and let $C$ be the set of cells, than the number of rectangles which are not of the form is at least half the number of bend shapes which are increasing. This is equal to: \[\sum_{i\in C}(n-f(i)-1)g(i)+(n-g(i)-1)f(i)\]Which by rearrangement inequality is minimsed when $f(i)=g(i)$, thus giving us our minimum.

Really beautiful and perfectly placed at #9. The answer is $\frac 1{12} n^2(n+1)(n-1)$ rectangles. Proof of Bound: We consider pivots, or cells $a, b, c$ such that $a$ and $b$ share a row, $b$ and $c$ share a column, and $b > a$ and $b>c$. Claim: There are at most $\frac 16n^2(n-1)(2n-1)$ pivots. Proof: For each cell $(i, j)$, denote by $a_{ij}$ the number of cells in the same row as $(i, j)$ with lesser value, and denote $b_{ij}$ to be the same number for the column. The number of pivots is given by the sum of $a_{ij}b_{ij}$ across all cells $(i, j)$. Observe that for any index $i$, \[\{a_{i1}, a_{i2}, \dots, a_{in}\} = \{0, 1, 2, \dots, n-1\} = \{b_{i1}, b_{i2}, \dots, b_{in}\}\]so by the Rearrangement inequality, \[\sum_{j=1}^n a_{in}b_{in} \leq \sum_{j=1}^n j^2 = \frac 16n(n-1)(2n-1).\]Summing across all columns yields the result. $\blacksquare$ Suppose that there are $x$ rectangles that satisfy the condition. Then among the vertices of each of these $x$ rectangles, we can find exactly two pivots; conversely, among the vertices of any of the $y$ remaining rectangles, we can find precisely one pivot. If there are $P$ pivots, it follows that \begin{align*} x &= (x+2y) - (x+y) = P - {n \choose 2}^2 \\ &\leq \frac 16n^2(n-1)(2n-1) - \frac 14 n^2(n-1)^2 = \frac 1{12} n^2(n+1)(n-1) \end{align*}as required. Construction: We just need the bound in the claim to be tight. A valid construction (among many) is to take the number in position $(i, j)$ to be $i + n(j-i) \pmod {n^2}$; see the $n=5$ case as an illustration: \[\begin{tabular}{ccccc} 1 & 6 & 11 & 16 & 21 \\ 22 & 2 & 7 & 12 & 17 \\ 18 & 23 & 3 & 8 & 13 \\ 14 & 19& 24 & 4 & 9 \\ 10 & 15 & 20 & 25 & 5 \end{tabular}\]