Spiraling

Unfortunately, even though you tried everything to defend against the hacking attack, they were able to access our network and unleash a horde of AI bots towards our routers, switches and servers. Their aim is to disrupt the contest! Luckily these bots are very basic and only work based on a rewarding system, so they just move round and round and if they find a server of lower value than the previous one they simply stop. Your task is to decide if a given robot is able to reach the most valuable server or not.

Input

The input is an n x n matrix based on the following:

• The first line is an n positive, odd integer, which gives you the number of rows and columns of the matrix.
• Each of the following n lines consists of n integers, separated by a single space character.
• The first number of the first line is the [0][0] index of the matrix and the last number of the last line is the [n-1][n-1] index.

Note: at the end of every input line there is an end of line character.

Output

The output is the integer 1 if starting to the right from the middle element of the given M matrix (so the element az place M[(n-1)/2][(n-1)/2]) and moving towards the M[0][0] element spirally counter-clockwise every element (including M[0][0] is greater-equal than the previous one.

Otherwise the output is the integer 0.

Example

Explanation

In the first case our starting number is 13 and since start to the right, our next element is 14. Since we move counter-clockwise as a spiral, then we get the following sequence up until the [0][0] element:
13-14-9-8-7-12-17-18-19-20-15-10-5-4-3-2-1
Since this sequence is not monotonically increasing, then the answer is 0.

In the second case our starting number is 5 and since start to the right, our next element is 6. Since we move counter-clockwise as a spiral, then we get the following sequence up until the [0][0] element:
5-6-7-8-9
Since this sequence is monotonically increasing, then the answer is 1.