Start by noting that we always have \(LIS + LDS \le N+1\), as increasing subsequence and decreasing subsequence can’t share more than one element.

By writing bruteforce you can notice that the total number of permutations with \(LIS+LDS = N+1\) is equal to \(\binom{2N-2}{N-1}\). For those of you who don’t know the Robinson–Schensted correspondence this might be surprising (and it was to me too as I didn’t know it when solving the problem).

Let’s interpret permutations as sets of \(N\) cells in a \(N\times N\) matrix, no two of which lie on the same row/column. Increasing subsequence here is a sequence of cells that go to the right and up, decreasing \(-\) to the right and down. Let’s call such sets with \(LDS + LIS = N+1\) good.

Now, consider \(N-1\) vertical lines, separating adjacent columns, and \(N-1\) horizontal lines, separating adjacent rows. We will define the bijection between good sets and the ways to choose \(N-1\) of those \(2(N-1)\) lines. First, let’s denote the point at the intersection of the \(i\)-th horizontal line and \(j\)-th vertical line by \([i, j]\). Don’t confuse this with cells! \([i, j]\) is a lower-right corner of the cell \((i, j)\).

Let’s choose any \(N-1\) of these lines. It’s the same as to choose an equal number of horizontal and vertical lines. Let’s say we chose \(K\) horizontal and vertical lines, call them blue. Call the remaining \(2(N-1-K)\) lines yellow.

Consider the \(i\)-th (from the left) blue vertical line, and \(i\)-th (from the up) blue horizontal line. Mark the point at their intersection blue.

Similarly, consider the \(i\)-th (from the right) yellow vertical line, and \(i\)-th (from the up) yellow horizontal line. Mark the point at their intersection yellow. Note that currently, we are marking points, not cells.

We now have \(N-1\) marked points, \(K\) blue and \(N-1-K\) yellow. It’s clear that all of them lie on distinct lines. Also it’s clear that all blue points form a decreasing path, and all yellow points form an increasing path.

Now, let’s select some cells. For every blue point \([a, b]\), do the following:

• Look at the region to the right and down to it. If there are no yellow points there, select cell \((a+1, b+1)\), and paint it in blue.

• Look at the region to the left and up to it. If there are no yellow points there, select cell \((a, b)\), and paint it in blue.

For every yellow point \([a, b]\), do the following:

• Look at the region to the right and up to it. If there are no blue points there, select cell \((a, b+1)\), and paint it in yellow.

• Look at the region to the left and down to it. If there are no blue points there, select cell \((a+1, b)\), and paint it in yellow.

We now prove several easy claims about these selected cells.

• For every blue point \([a, b]\), we selected at least one of cells \((a, b), (a+1, b+1)\). Indeed, otherwise, there would be yellow cells in both upper-left and lower-right regions, but this can’t happen, as yellow cells form an increasing sequence.

• Similarly, we selected at least one of cells \((a, b+1), (a+1, b)\) for every yellow point.

• Blue points \([a, b]\) for which we selected cell \((a, b)\) form a prefix of all blue points, and those for which we selected cell \((a+1, b+1)\) form a suffix.

• Yellow points \([a, b]\) for which we selected cell \((a, b+1)\) form a prefix of all yellow points, and those for which we selected cell \((a+1, b)\) form a suffix.

Now, let’s show that no blue cell is in the same row as some yellow cell, and no blue cell is in the same column as some yellow cell. Suppose that some yellow cell is in the same row as some blue cell. (For columns, everything is symmetric). Let’s say that cell \((x, y_1)\) is blue and \((x, y_2)\) is yellow. First, we can’t have \(y_1 = y_2\), as then we would get that some yellow point and some blue point have the same \(x\)-coordinate or the same \(y\)-coordinate, which is impossible (the point from which a cell was colored has to be a corner of this cell; for blue: lower-right or upper-left, for yellow lower-left or upper-right). Now, consider two cases:

1. \(y_1<y_2\). If the blue point was \([x, y_1]\) and yellow was \([x-1, y_2]\), then we wouldn’t have colored \([x, y_2]\) yellow, as there is a blue point in the lower-left region of the yellow point. If the blue point was \([x-1, y_1-1]\) and yellow was \([x, y_2-1]\), then we wouldn’t have colored \([x-1, y_1-1]\) blue, as there is a yellow point in the lower-right region of the blue point.

2. \(y_1>y_2\). The same argument, won’t repeat it.

Note that while we proved that the cell can’t be painted both blue and yellow, it can still be painted blue several times (or yellow several times).

Now, let’s show that two different blue cells can’t be in the same row/column (and the same for yellow). Suppose that some two blue cells are in the same row, say, \((x, y_1), (x, y_2)\) with \(y_1<y_2\). Then we must have painted cell \((x, y_1)\) from \([x-1, y_1-1]\) and cell \((x, y_2)\) from \([x, y_2]\), and that these are “consecutive” blue points. As \(y_1 - 1 < y_2\), this would mean that there is a yellow point in the \(y_1\)-st vertical line. But the fact that we colored these cells implies that there can’t be any yellow point there, contradiction,

So, we got that there are at least \(K\) blue cells, at least \(N-1-K\) yellow, and at most \(N\) cells in total (as no two different painted cells share a column or a row). So, we have two cases.

• There are \(N\) painted cells. Then we are done with painting. Let’s show that \(LIS+LDS = N+1\) for the set of cells consisting of painted cells. It’s clear that \(LDS \ge K, LIS \ge N-K-1\). Note that if for each point we would paint only one cell, we would paint only \(N-1\) cells. So, wlog, for some blue point \([a, b]\) we painted both \((a-1, b-1)\) and \((a, b)\). Then \(LDS \ge K+1\). Also this means that all yellow cells are below and to the left or up and to the right of this point so that we can include the cell \((a, b)\) into the increasing sequence of yellow cells. So, we would get \(LIS \ge N-K\), and \(LIS + LDS \ge N+1\).

• There are \(N-1\) painted cells. Then look at the column and the row where no cell is painted, and denote the cell at their intersection by \((x, y)\). Then, select this cell together with \(N-1\) painted cells. We will show that this set would also have \(LIS + LDS = N+1\). But first, let’s analyze this case a little. Note that \(N-1\) painted cells \(\implies \) from each point we painted only one cell. It’s easy to see then that for all points above (and including) \(x-1\)-st horizontal line, we painted the upper cell (among two options), and for all below, we painted the lower cell. Similarly, to the left of \(y-1\)-st horizontal line, we painted the left cell, and to the right, we painted the right cell. Then to the left and up we were painting only left-up cells, which means that we were doing this only for blue points. It follows that only blue cells can be to the left-up from \((x, y)\) and to the right-down (similarly). Similarly, only yellow cells can be to the right-up from \((x, y)\) and to the left-down. Then selecting cell \((x, y)\) would indeed increase the length of both \(LIS\) and \(LDS\) by \(1\), making \(LIS + LDS = N+1\).

I have finally fully specified the direction (choice of lines \(\to\) permutation with \(LIS + LDS = N+1\)). I won’t prove that it’s an injection, but you can do this yourself. In the remaining part of the editorial, I will show how to use this to count the number of permutations satisfying the condition from the problem.

First, we have to count the number of ways to select these blue/yellow rows, so that the cell \((pos, val)\) would be painted. Let’s count the number of times it will be painted blue. What’s the number of times it will be painted from the point \([x-1, y-1]\)?

Iterate over \(t -\) the index of this blue point \([x-1, y-1]\) (so that we have to choose exactly \(t\) horizontal lines among first \(x-1\) and exactly \(t\) vertical among first \(y-1\), the number of ways to do this is \(\binom{x-2}{t-1}\cdot \binom{y-2}{t-1}\)). Then we would choose \(x-1-t\) yellow and \(y-1-t\) yellow ones. The condition that there are no yellow points to the right and below of \([x-1, y-1]\) is equivalent to \(N-1-K\) being at most \((x-1-t) + (y-1-t)\). So, we get \(N-1-K \le x+y-2-2t \iff K\ge N+1+2t-x-y \implies \) we have to choose at least \(N+1+t-x-y\) more blue lines. The number of ways to choose \(t_1\) more blue lines is \(\binom{N-x}{t_1}\cdot \binom{N-y}{t_1}\). We have to find the sum of these for some segment of \(t_1\), which we can do with prefix sums.

Count similarly the number of times it will be painted from the point \([x, y]\), and then subtract the number of times it will be painted from both (calculate with ideas same as above). Then do the same for yellow cells.

It remains to count the number of times cell \((x, y)\) will be painted as the “remaining cell” in the case of \((N-1)\) yellow+blue cells. Well, we can do that similarly, too. Just iterate over \(t -\) the number of blue lines you select to the left and above, all numbers of cells are determined uniquely, and the only restriction is: you can’t allow points \([x-1, y-1], [x, y], [x-1, y], [x, y-1]\) be painted (then cell \((x, y)\) would turn out painted). Do this with some more inclusion-exclusion.

The total complexity is \(O(N)\).

Bonus: Find all typos.