Ở một xã vùng cao có ~N~ hộ gia đình được đánh số từ ~1~ đến ~N~. Do mạnh dạn áp dụng khoa học kỹ thuật vào làm kinh tế nên trong xã có nhiều hộ gia đình đã trở nên giàu có. Trong kỳ tổng kết cuối năm vừa qua, chính quyền xã biết được hộ gia đình thứ ~i~ ~(1 \le i \le N)~ có thu nhập là ~A_i^{(0)}~. Hưởng ứng phong trào toàn dân làm kinh tế nâng cao thu nhập và thu hẹp khoảng cách giàu nghèo, bắt đầu từ năm nay, gọi là năm thứ nhất, hàng năm chính quyền xã yêu cầu với mỗi hộ gia đình, hộ thứ ~i~ ~(1 \le i \le N)~ phải nghiên cứu phương thức làm kinh tế năm trước của các hộ gia đình liên tiếp từ thứ ~L_i~ đến thứ ~R_i~ ~(1 \le L_i \le R_i \le N)~ để học hỏi kinh nghiệm.

Với mỗi hộ gia đình ~X~, nếu thu nhập năm trước lớn hơn hoặc bằng thu nhập của hộ có thu nhập cao nhất trong số các hộ gia đình mà hộ ~X~ phải học hỏi, thì hộ ~X~ giữ nguyên phương thức làm kinh tế cũ sao cho năm nay sẽ có thu nhập ổn định bằng năm trước. Trái lại, hộ ~X~ sẽ phải sửa đổi phương thức làm kinh tế với sự hỗ trợ của chính quyền sao cho thu nhập năm nay của hộ ~X~ sẽ phải bằng thu nhập cao nhất năm trước trong số các hộ mà hộ ~X~ học hỏi. Cụ thể, tại năm thứ ~t~ ~(t \ge 1)~, hộ gia đình thứ ~i~ ~(1 \le i \le N)~ sẽ có thu nhập là ~A_i^{(t)} = max(A_i^{(t - 1)}, A_{L_i}^{(t - 1)}, A_{L_{i + 1}}^{(t - 1)}, \ldots, A_{R_i}^{(t - 1)})~.

Yêu cầu: Hãy giúp chính quyền xác định bắt đầu từ năm thứ bao nhiêu thì mỗi hộ gia đình đều sẽ có thu nhập ổn định năm sau bằng năm trước.

Dữ liệu

Vào từ file văn bản INCOME.INP:

• Dòng đầu chứa một số nguyên dương ~N~ ~(N \le 3 \times 10^5)~.

• Dòng thứ hai chứa ~N~ số nguyên dương ~A_1^{(0)}, A_2^{(0)}, \ldots, A_N^{(0)}~ ~(A_i^{(0)} \le 10^9, \forall{i} = 1, 2, \ldots, N)~.

• Dòng thứ ~i~ trong số ~N~ dòng tiếp theo chứa hai số nguyên dương ~L_i~ và ~R_i~ ~(L_i \le R_i \le N)~.

Các số trên cùng một dòng cách nhau bởi dấu cách.

Kết quả

Ghi ra file văn bản INCOME.OUT một số nguyên ~t~ là năm mà bắt đầu từ đó trở đi, mỗi hộ gia đình đều có thu nhập ổn định năm sau bằng năm trước.

Ràng buộc

• Có ~18\%~ số test ứng với ~18\%~ số điểm thỏa mãn: ~N \le 500~.

• ~16\%~ số test khác ứng với ~16\%~ số điểm thỏa mãn: ~A_i^{(50)} = A_i^{(49)}, \forall{i} = 1, 2, \ldots, N~.

• ~20\%~ số test khác ứng với ~20\%~ số điểm thỏa mãn: ~\sum_{i=1}^n (R_i - L_i) \le 10^6~.

• ~24\%~ số test khác ứng với ~24\%~ số điểm thỏa mãn: Không tồn tại ~i, j~ ~(1 \le i, j \le N)~ thỏa mãn ~L_i \lt L_j~ và ~R_j \lt R_i~.

• ~22\%~ số test còn lại ứng với ~22\%~ số điểm không có ràng buộc gì thêm.

Ví dụ

Input

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

Output

3

Giải thích

• Ở năm đầu tiên, thu nhập các hộ lần lượt là ~(2, 3, 3, 4)~.

• Ở năm thứ hai, thu nhập các hộ lần lượt là ~(3, 3, 3, 4)~.

• Từ năm thứ ba trở đi, thu nhập của các hộ giữ nguyên là ~(3, 3, 3, 4)~.