TLEOJ [x QTOJ] Contest #13 - E - Hai lần trung vị

Điểm: 1900

Thời gian: 1.0s

Python 3 5.0s

Bộ nhớ: 512M

Input: bàn phím

Output: màn hình

Tác giả:

Dạng bài

Bạn được cho một dãy $a_1, a_2, ..., a_n$ . Xét $b$ là dãy gồm các trung vị của các đoạn con liên tiếp của $a$ , hãy tính trung vị của $b$ .

Nhắc lại:

Trung vị của một dãy $x_1, x_2, ..., x_n$ đã được sắp xếp là $x_{[\frac{n + 1}{2}]}$ , với $[i]$ là số nguyên lớn nhất không lớn hơn $i$ .
Một đoạn con liên tiếp của một dãy $y_1, y_2, ..., y_n$ là một dãy $a_l, a_{l + 1}, ..., a_r$ với $1 \le l \le r \le n$ .

Input và Output

Input (bàn phím)

Dòng đầu tiên gồm một số nguyên dương $n$ là số lượng phần tử $(1 \le n \le 10^6)$ .
Dòng thứ hai gồm $n$ số nguyên dương $a_1, a_2, ..., a_n$ $(1 \le a_i \le 10^9)$ .

Output (màn hình)

Sample 1

Input (bàn phím)

4
1 2 3 4

Output (màn hình)

Note

Dãy $(1), (2), (3), (4)$ có trung vị lần lượt là $1, 2, 3, 4$ .
Dãy $(1, 2), (2, 3), (3, 4)$ có trung vị lần lượt là $1, 2, 3$ .
Dãy $(1, 2, 3), (2, 3, 4)$ có trung vị lần lượt là $2, 3$ .
Dãy $(1, 2, 3, 4)$ có trung vị là $2$ .
Vậy dãy $b=(1,2,3,4,1,2,3,2,3,2)$ có trung vị là $2$ .

Sample 2

Input (bàn phím)

4 
1 1 2 2

Output (màn hình)

Sample 3

Input (bàn phím)

4 
4 3 2 1

Output (màn hình)

Bình luận

Không có bình luận nào.