A grasshopper is in a flower field. The field contains
The grasshopper is initially on the flower in row
It can only jump into an adjacent row or column. If it jumps into the adjacent row, it must jump at least two columns, and if it jumps into the adjacent column, it must jump at least two rows.
In other words, it can jump from flower
to flower if: and or and
The number of petals on the next flower must be strictly larger than the number of petals on the previous flower.
Write a program that calculates the largest number of flowers the grasshopper can visit.
Input Specification
The first line contains the integer
The second line contains integers
The next
Output Specification
Output a single integer – the largest number of flowers the grasshopper can visit.
Grading
In test data worth
Sample Input 1
4
1 1
1 2 3 4
2 3 4 5
3 4 5 6
4 5 6 7
Sample Output 1
4
Sample Input 2
5
3 3
20 16 25 17 12
11 13 13 30 17
15 29 10 26 11
27 19 14 24 22
23 21 28 18 13
Sample Output 2
21
Comments