시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 3 2 2 66.667%

문제

A large number of books have arrived to the library of the Aglargond School of Magic and they need to be arranged on the shelves. On the library floor, tiled with equal square tiles, librarians marked a square‐shaped area (length of the side of this square is N square tiles) for temporary storage of the books. Books were either stacked on top of the other books or on the empty tiles in the marked area in such fashion that a stack of books is formed on some tiles. The youngest student got an assignment to enter information about every book into the catalogue and arrange the books to their shelves. After hearing this news he just stood beside the books and sighed burdened by the amount of work he had to do. Going alongside the edges of the marked area he looks in directions parallel to sides of the marked area and counts stacks of books visible. A stack is visible if there is no higher stack or stack with equal height between it and the student. Write a program that counts the number of stacks visible to the young magician while walking beside the books.

입력

The first line of input contains length of the side 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 character, representing heights of stacks (in cm) of books on each floor tile. If there are no books on a tile, height of the stack is 0.

출력

The output should contain the number of visible stacks.

예제 입력 1

4
3 3 2 1
4 1 0 2
3 2 0 0
3 1 2 1

예제 출력 1

12

힌트

Stack on the position (2, 2) is not visible and tiles (2, 3), (3, 3) and (3, 4) have no books on it.