Trong một khu bảo tồn thiên nhiên hoang dã rộng lớn, các nhà khoa học đã phát hiện ra một quần thể sinh vật độc đáo có ~n~ cá thể. Để nghiên cứu sự đa dạng sinh học của quần thể này, họ đã gắn cho mỗi cá thể một thẻ nhận dạng điện tử với một mã số duy nhất. Mã số này không chỉ giúp phân biệt các cá thể mà còn cung cấp thông tin về loài của chúng, các con cùng loài sẽ có mã số giống nhau, các con khác loài sẽ có mã số khác nhau.

Sau khi điền các mã số vào danh sách, ta được 1 danh sách ~A~ gồm ~A_1~ , ~A_2~,..., ~A_n~ là các mã số của từng con

Các nhà khoa học đã phát triển một hệ thống ~f(i,j)~ có khả năng quét và ghi nhận mã số của các cá thể từ ở đoạn khu vực ~i~ đến ~j~ của danh sách ~A~ với ~i \le j~. Hệ thống này sẽ tính toán giá trị đa dạng sinh học của đoạn đó, tức là số lượng loài khác nhau trong đoạn.Hệ thống này sẽ quét qua tất cả các đoạn có thể. Kết quả cuối cùng là một danh sách ~D~,hay nói các khác ta có danh sách ~D~ ~=~ ~\lbrace~ ~f(i,j) ,1\le i\le j \le n~ ~\rbrace~

Dữ liệu thu thập được sẽ được truyền về một máy chủ trung tâm để xử lý.Để đánh giá mức độ đa dạng sinh học của khu rừng, các nhà khoa học đã chọn ra "đại diện tiêu biểu" - giá trị trung vị của danh sách ~D~.

Trung vị của một danh sách được xác định là phần tử ở giữa của danh sách khi nó được sắp xếp theo thứ tự không giảm. Nếu có hai lựa chọn cho giá trị trung vị thì giá trị nhỏ hơn trong hai giá trị sẽ được chọn.

Input

Dòng đầu ghi số nguyên ~n~ ~(1 \le n \le 10^5)~

Dòng tiếp theo ghi ~n~ số nguyên ~A_i~ ~(1 \le A_i \le 10^5)~

Output

In ra trung vị của dãy ~D~

Sample Input 1

3
1 2 3

Sample Output 1

1

Sample Input 2

5
3 4 3 4 5

Sample Output 2

2

Giải thích

Test 1:

Danh sách ~D~ ~=~ ~[~ ~f(0,0)~, ~f(1,1)~, ~f(2,2)~, ~f(0,1)~, ~f(1,2)~, ~f(0,2)~ ~]~=~[~ ~1~, ~1~, ~1~, ~2~, ~2~, ~3~]

Trung vị của ~D~ bằng ~1~

Test 2:

Danh sách ~D~ ~=~ ~[~ ~1~, ~1~, ~1~, ~1~, ~1~, ~2~, ~2~, ~2~, ~2~, ~2~, ~2~, ~2~, ~3~, ~3~, ~3~ ~]~

Trung vị của ~D~ bằng ~2~