Piles of Books

Interview

Time limit1sMemory limit512 MB

Summary

Count the tiles whose pile height is strictly greater than every pile between it and the boundary along the student's line of sight from all four sides.

Level: Medium4 of 10
Topics: Array, Implementation, Simulation, Brute force
Solved: No attempts yet

Problem

A large number of books have arrived at the library of the Aglargond School of Magic, and they need to be arranged on the shelves. The library floor is tiled with equal square tiles, and the librarians marked a square area (side length N tiles) for temporary storage of the books. Books were either stacked on top of other books or placed on empty tiles inside the marked area, so a pile of books formed on some tiles. The youngest student was assigned to enter information about every book into the catalogue and arrange the books on their shelves. When he heard the news, he just stood beside the books and sighed at the amount of work he had to do. Walking along the edges of the marked area, he looks in directions parallel to the sides of the area and counts the visible piles of books. A pile is visible if there is no higher pile or pile of equal height between it and the student. Write a program that counts the number of piles visible to the young magician while walking beside the books.

Input

The first line of input contains the side length of the marked area, N (1 ≤ N ≤ 50). Each of the next N lines contains N non-negative integers not greater than 1000 separated by single space characters, representing the heights of the piles (in cm) of books on each floor tile. If there are no books on a tile, the height of the pile is 0.

Output

The output should contain the number of visible piles.

Hint

The pile at position (2, 2) is not visible, and tiles (2, 3), (3, 3) and (3, 4) have no books on them.

Examples1

Example 1
Input
```
4
3 3 2 1
4 1 0 2
3 2 0 0
3 1 2 1
```
Expected output
```
12
```