Ở một trường P nọ, các học sinh rất thích tiết thể dục. Thầy giáo dạy thể dục thường cho khởi động từ giữa
hàng, tức là thầy sắp xếp học sinh theo chiều cao từ nhỏ đến lớn, lúc này bạn khởi động đầu tiên là bạn ở giữa
hàng nếu hàng lẻ và bạn ở giữa hàng có chiều cao thấp hơn đối với hàng chẵn. Thầy giáo không nhớ tên học sinh
nhưng thầy ấy có thể ước lượng chiều cao của các nhóm học sinh đi vào sân thể dục.
Có n nhóm học sinh đi vào, nhóm thứ i có a[i] bạn và có chiều cao ước lượng như nhau là v[i].

Yêu cầu: Xác định chiều cao của bạn sẽ khởi động đầu tiên lần lượt theo thứ tự đi vào của các nhóm học sinh.

INPUT gồm nhiều dòng: dòng 1 chứa số nguyên dương n là số nhóm học sinh, n dòng tiếp theo mỗi
dòng chứa hai số nguyên dương v[i] và a[i] đại diện cho nhóm học sinh thứ i.

OUTPUT gồm nhiều dòng: dòng thứ i là chiều cao của học sinh sẽ khởi động khi các nhóm từ 1
đến i đã đi vào sân thể dục.

• 1 ≤ n ≤ 2e5.
• 1 ≤ v[i], a[i] ≤ 1e9.