Ami là người đặc biệt. Cậu không thích dẫn đầu, càng không thích về cuối, cậu chỉ thích những vị trí lưng chừng. Đó cũng là lí do vì sao 3 năm học cấp 3 sắp trôi qua mà cậu vẫn chưa một lần được giải nhất Hội Thi Tin Học Trẻ cấp thành phố.

Hằng ngày, Ami phải làm việc với rất nhiều dãy số, và với mỗi dãy số, và với mỗi dãy số, cậu đều tìm ra một số phần tử phù hợp với tính cách của mình, đó các phần tử ở giữa dãy. Cho một dãy gồm n số a₁,a₂,…,a_n đã được sắp xếp không giảm, phần tử ở giữa dãy là số hạng thứ (n + 1) div 2.

          Bây giờ, việc tìm phần tử ở giữa của 1 dãy số là điều quá đơn giản, Ami muốn tìm phần phần tử ở giữa của các dãy con liên tiếp bắt đầu từ 1 của dãy số đó. Các bạn được Ami phó thác cho nhiệm vụ quan trọng này.

Dữ liệu vào

Dòng đầu là một số nguyên dương n (n <= 3 * 10⁵) là số phần tử của dãy

Dòng tiếp theo gồm n số nguyên a₁,a₂,a₃,…,a_n (|a_i| <= 10⁹) là các phần từ của dãy.

Dữ liệu ra

Gồm n dòng, dòng thứ i là phần tử chính giữa của dãy a₁,a₂,…,a_i.