# [Excursion](https://po2punkt0.kattis.com/problems/vandring) - problem of the month June 2025

## $O(R^4)$
Let's think carefully how a walk can become uninteresting. It must be the case that there is some square with value $c$, and another square with value $c$ bottom-right relative to the first square. Let's call such a pair a "bad pair".
For example, the 5's here form a bad pair:

Most grids won't have all numbers drawn in them for the sake of visual clarity.

Therefore, one solution is to loop over each position, and for each of those, loop through all positions that are in the bottom-right quadrant of it.

This runs in $O(R^4)$ time.

## $O(R^3)$
There are ways to speed up the previous algorithm to $O(R^2\log(R))$ using advanced techniques. However, there are significantly easier ways.

One idea to speed things up is the following: instead of looping over which position to check from, let's loop over the value and check all of them at once. Initially, it seems like this does not help at all. However, the nice thing is that for each value, there can be at most $R$ of it without there being a bad pair. Below, I have draw a case with the most number of values without a bad pair. If we add any more 5's, there a bad pair will form.
So our algorithm is that for each value, we collect the positions of it. If any group has more than $R$ values, we say that not all walks are interesting. Otherwise, if the group has $N$ values, we check for each pair if it is bad in $O(N^2)$ time. It turns out that this means that the total runtime is bounded by $O(R^3)$. The worst case looks like a rainbow if each value has a color:

## $O(RC\log(R))$
Let's optimize the previous solution. Instead of processing each group of $N$ values in $O(N^2)$, we will do it in $O(N\log(N))$, leading to $O(RC\log(R))$ overall. To do this, let's sort the values so that the top ones come first. First, we will check if any two are on the same row, in which case no walk is interesting. Otherwise, we know that future values must be to the bottom-left of the current value. The disallowed area is drawn in red:

So in fact, we can do a single loop once our values are sorted: keep track of the (x,y) position of the last value and ensure that the subsequent value is to the bottom-left of it.

## Smart $O(RC)$ solution
While the previous solution is fast enough, there's a solution using even less code. We can realize that the sorting is unneeded, since if we iterate through the rows, it will be in sorted order. We can do all groups at once by, for each value keeping track of the leftmost occurence of it. If we ever find another value to the right of said value, it will be invalid. Code inspired by Movitz Sunar's solution:

R = int(input())
max_x = [R+1] * (R * R)

for i in range(R):
    for x, value in enumerate(map(int, input().split())):
        if max_x[value] < x:
            print(0)
            exit(0)
        max_x[value] = x

print(1)