Cô Q đang hợp tác với Viện Vật liệu tại Bắc Ninh để nghiên cứu vật liệu gốm xốp ứng dụng trong lọc nước. Lớp gốm này có cấu trúc đa por (đa lỗ) với độ không đồng nhất cao. Các thử nghiệm thực tế cho thấy khi áp dụng quy trình etching hóa học (khắc hóa học), các vùng có độ bền thấp (ngưỡng ăn mòn nhỏ) sẽ bị ăn mòn trước, hình thành lỗ rỗng lan dần. Khi ngưỡng ăn mòn T đủ lớn, sẽ xuất hiện một đường thông từ mặt trên đến mặt dưới, cho phép dòng nước xuyên qua

Trên cơ sở này, ta giả lập màng gốm xốp dưới dạng lưới vuông có kích thước 𝑁×𝑁. Mỗi ô (i,j) có độ bền vật liệu (ngưỡng ăn mòn) a_(i,j). Khi etch ở mức T, ô bị ăn mòn (rỗng) nếu a_(i,j) ~\le T~, ngược lại vẫn đặc. Khi T tăng dần, càng nhiều ô bị ăn mòn, và có thể sẽ xuất hiện một đường thông từ hàng trên cùng xuống hàng dưới cùng, cho phép nước thấm xuyên qua màng. Cô Q quan tâm: ngưỡng tối thiểu T để dòng nước thấm từ hàng trên cùng xuống hàng dưới cùng và có thể đi qua màng.

Yêu cầu: Tìm giá trị nhỏ nhất T sao cho khi đánh dấu tất cả các ô có a_(i,j) ~\le T~ là rỗng, tồn tại một đường đi liên thông qua các ô rỗng từ ô bất kỳ thuộc hàng đầu tiên đến bất kỳ ô thuộc hàng N.

Định nghĩa về liên thông: Hai ô được gọi là liên thông nếu:

• Chúng đều là ô rỗng, và
• Chúng kề cạnh nhau theo 1 trong 4 hướng cơ bản: Trên, dưới, trái, phải.

Dữ liệu vào:

• Dòng đầu tiên chứa số nguyên N.
• N dòng tiếp theo, mỗi dòng gồm N số tự nhiên biểu thị ngưỡng ăn mòn.

Dữ liệu ra:

• Kết quả T là giá trị ngưỡng nhỏ nhất.

Input:

3
5 4 7
6 2 8
9 1 3

Output:

4

Giải thích:

• Với T = 4, thì các ô có giá trị 4, 2, 1 sẽ tạo thành 1 thành phần liên thông từ hàng 1 tới hàng N.

Giới hạn:

• ~1 \le N \le 10^{3}~.
• ~0 \le a_{i,j} \le 10^{9}~.