문제

가을이 되면서, 단풍나무가 물들기 시작하려고 한다. 구름공원에서는 크기가 인 땅에 단풍나무를 많이 심어두었다.

구름공원은 땅을 효율적으로 관리하기 위해, 땅을  크기의 작은 구역 단위로 나눈 뒤 해당 구역에 심어진 나무들을 묶어서 관리하고 있다. 공원의 위쪽에서 번째, 왼쪽에서 번째에 위치한 구역의 이름은 이다.

현재 구름 공원의  구역에는  그루의 물들지 않은 단풍나무가 있다. 단풍나무는 아래 규칙에 따라 물들어간다.

• 의 값이 이면, 해당 구역의 모든 단풍나무가 물들었음을 의미한다.
• 는 매일 밤마다 상하좌우로 인접한 구역 중 그날 아침 기준으로 단풍나무가 모두 물들어 있는 구역의 수만큼 줄어든다. 만약 그러한 구역의 수가 보다 크다면, 의 값은 이 된다.

구름공원에는 모든 단풍나무가 물들어 있는 구역이 최소 한 곳 이상은 존재한다고 할 때, 며칠 후에 모든 단풍나무가 물들지 출력하시오.

예제 설명

첫 번째 예제에서 구름공원의 상태는 아래 그림과 같다.

첫째 날에는 규칙에 따라 아래와 같은 칸들이 물들게 된다.

• 의 값은 1이고, 상하좌우에 단풍나무가 모두 물든 구역은 두 곳이다. 그래서 단풍나무는 두 그루까지 물들 수 있지만, 남아있는 단풍나무가 한 그루이기 때문에 한 그루만 물들고, 의 값은 0이 된다.
• 의 값은 2이고, 인접한 구역 중 단풍나무가 모두 물든 구역은 두 곳이다. 단풍나무는 두 그루가 물들 수 있고, 의 값은 0이 된다.
• 과 의 값은 2이고, 인접한 구역 중 단풍나무가 모두 물든 구역은 두 구역 모두 한 곳이다. 그래서 두 구역 모두 한 그루의 단풍나무가 물들고, 과 의 값은 모두 1이 된다.

이후 둘째 날과 셋째 날이 지나고 나면 공원의 상태는 아래와 같이 변한다. 3일이 지난 뒤에 모든 단풍나무가 물들었음으로 3을 출력해야 한다.

입력

첫째 줄에 공원의 크기를 나타내는 이 주어진다.
다음 개의 줄에는 매 줄마다 이 공백을 두고 주어진다.

• 
• 
• 단풍나무가 모두 물든 구역이 하나 이상 존재한다.
• 입력에서 주어지는 모든 수는 정수이다.
  

출력

구름공원의 모든 단풍나무가 물드는데 며칠이 걸리는지 출력하시오.