สำหรับมัลติเซต $S=\{x_0,x_1,\ldots,x_{m-1}\}$ ขนาด $m$ สมมติว่าเมื่อเรียงสมาชิกทั้งหมดจากมากไปน้อยได้ $y_0 \ge y_1 \ge \cdots \ge y_{m-1}$ นิยามมัธยฐาน $Median(S)$ ว่าเป็นจำนวนที่มากเป็นอันดับ $\lceil m/2\rceil$ นั่นคือ $Median(S)=y_{\lceil m/2\rceil-1}$ โปรดทราบ: นิยามมัธยฐานในโจทย์นี้อาจแตกต่างจากนิยามทั่วไป

กำหนดลำดับ $[a_0,a_1,\ldots,a_{n-1}]$ ความยาว $n$ และจำนวนเต็มบวก $k$ ($k \le n$) นิยามการแบ่งดังนี้: เลือกลำดับดัชนีเพิ่มขึ้นความยาว $k-1$ ซึ่ง $0<b_1<\cdots<b_{k-1}<n$ ก็จะแบ่งลำดับเดิมเป็น $k$ ช่วง โดยมีช่วงดัชนีตามลำดับคือ $[0,b_1),[b_1,b_2),\ldots,[b_{k-1},n)$

สำหรับการแบ่งหนึ่งแบบ นิยามค่าความสมดุลดังนี้: คำนวณมัธยฐานของมัลติเซตที่ประกอบด้วยสมาชิกทั้งหมดของแต่ละช่วงที่แบ่งได้ มัธยฐานของมัลติเซตที่ประกอบด้วยมัธยฐานทั้ง $k$ ค่านี้คือค่าความสมดุลของการแบ่งนั้น กล่าวอย่างเป็นทางการ สำหรับการแบ่ง $b_1,\ldots,b_{k-1}$ ให้ $b_0=0,b_k=n$ และให้มัธยฐานของสมาชิกทั้งหมดในช่วงที่ $i$ ($0 \le i<k$) เป็น $c_i=Median(\{a_{b_i},a_{b_i+1},\ldots,a_{b_{i+1}-1}\})$ ค่าความสมดุลของการแบ่งนี้คือ $Median(\{c_0,\ldots,c_{k-1}\})$

จงหาค่าความสมดุลมากที่สุดในบรรดาการแบ่งทั้งหมด

รายละเอียดการเขียนโปรแกรม

ผู้เข้าแข่งขันไม่จำเป็นต้อง และไม่ควรเขียนฟังก์ชัน main

ผู้เข้าแข่งขันต้องทำให้แน่ใจว่าไฟล์ซอร์สโค้ดที่ส่งรวมเฮดเดอร์ median.h โดยเพิ่มโค้ดต่อไปนี้ที่ต้นโปรแกรม:

#include "median.h"

ผู้เข้าแข่งขันต้องเขียนฟังก์ชันสองตัวต่อไปนี้ในไฟล์ซอร์สโค้ด median.cpp ที่ส่ง:

void init(int c, int t);

• $c,t$ แทนหมายเลขกรณีทดสอบและจำนวนชุดข้อมูลตามลำดับ $c=0$ หมายความว่ากรณีทดสอบนี้เป็นตัวอย่าง
• สำหรับแต่ละกรณีทดสอบ โปรแกรมประเมินจะเรียกฟังก์ชันนี้หนึ่งครั้งพอดีเมื่อเริ่มทำงาน

int median(int n, int k, std::vector<int> a);

• $n,k,a$ แทนความยาวลำดับ จำนวนช่วงที่แบ่ง และลำดับที่กำหนดตามลำดับ
• ฟังก์ชันนี้ต้องคืนค่าความสมดุลมากที่สุด
• สำหรับแต่ละกรณีทดสอบ โปรแกรมประเมินจะเรียกฟังก์ชันนี้ $t$ ครั้งพอดี

ไฟล์ template_median.cpp ในไดเรกทอรีโจทย์เป็นโค้ดตัวอย่างที่จัดเตรียมให้ ผู้เข้าแข่งขันใช้เป็นแนวทางและเขียนโค้ดของตนเองได้

วิธีทดสอบโปรแกรม

ผู้เข้าแข่งขันใช้คำสั่งต่อไปนี้ในไดเรกทอรีโจทย์เพื่อคอมไพล์เป็นไฟล์ปฏิบัติการได้:

g++ grader.cpp median.cpp -o median -O2 -std=c++14 -static

สำหรับไฟล์ปฏิบัติการ median ที่คอมไพล์ได้:

• ไฟล์ปฏิบัติการจะอ่านข้อมูลจากข้อมูลนำเข้ามาตรฐานตามรูปแบบต่อไปนี้:

บรรทัดแรกมีจำนวนเต็มไม่เป็นลบสองจำนวน $c,t$

จากนั้นเป็นข้อมูลแต่ละชุดตามลำดับ สำหรับแต่ละชุด:

บรรทัดแรกมีจำนวนเต็มบวกสองจำนวน $n,k$

บรรทัดที่สองมีจำนวนเต็มบวก $n$ จำนวน $a_0,a_1,\ldots,a_{n-1}$

• ไฟล์ปฏิบัติการจะพิมพ์ข้อมูลไปยังข้อมูลส่งออกมาตรฐานตามรูปแบบต่อไปนี้:

สำหรับแต่ละชุดข้อมูล พิมพ์จำนวนเต็มบวกหนึ่งจำนวนในหนึ่งบรรทัด แทนค่าความสมดุลมากที่สุด

ตัวอย่าง

ข้อมูลนำเข้า 1

0 2
10 4
6 5 1 9 2 3 10 7 4 8
10 5
5 7 3 10 8 2 9 1 6 4

ข้อมูลส่งออก 1

9
8

หมายเหตุ

สำหรับข้อมูลชุดแรก การแบ่งที่มีค่าความสมดุลมากที่สุดแบบหนึ่งคือ $b_1=3,b_2=5,b_3=7$ ซึ่งแบ่งลำดับเดิมเป็น 4 ช่วง $[6,5,1],[9,2],[3,10],[7,4,8]$ มัธยฐานของสมาชิกทั้งหมดในแต่ละช่วงตามลำดับคือ $5,9,10,7$ ดังนั้นค่าความสมดุลของการแบ่งนี้คือ $Median(\{5,9,10,7\})=9$

สำหรับข้อมูลชุดที่สอง การแบ่งที่มีค่าความสมดุลมากที่สุดแบบหนึ่งคือ $b_1=2,b_2=4,b_3=6,b_4=8$ ซึ่งแบ่งลำดับเดิมเป็น 5 ช่วง $[5,7],[3,10],[8,2],[9,1],[6,4]$ มัธยฐานของสมาชิกทั้งหมดในแต่ละช่วงตามลำดับคือ $7,10,8,9,6$ ดังนั้นค่าความสมดุลของการแบ่งนี้คือ $Median(\{7,10,8,9,6\})=8$

ตัวอย่าง 2

ดูไฟล์ median/median2.in และ median/median2.ans ในไดเรกทอรีของผู้เข้าแข่งขัน

ตัวอย่างนี้ตรงตามข้อจำกัดของกรณีทดสอบที่ $6$

ตัวอย่าง 3

ดูไฟล์ median/median3.in และ median/median3.ans ในไดเรกทอรีของผู้เข้าแข่งขัน

ตัวอย่างนี้ตรงตามข้อจำกัดของกรณีทดสอบที่ $9$

ตัวอย่าง 4

ดูไฟล์ median/median4.in และ median/median4.ans ในไดเรกทอรีของผู้เข้าแข่งขัน

ตัวอย่างนี้ตรงตามข้อจำกัดของกรณีทดสอบที่ $14$

ตัวอย่าง 5

ดูไฟล์ median/median5.in และ median/median5.ans ในไดเรกทอรีของผู้เข้าแข่งขัน

ตัวอย่างนี้ตรงตามข้อจำกัดของกรณีทดสอบที่ $18$ ถึง $20$

ข้อจำกัด

ให้ $N$ เป็นผลรวมของ $n$ ในข้อมูลทุกชุดภายในกรณีทดสอบหนึ่ง สำหรับข้อมูลทดสอบทั้งหมด มี:

• $1 \le t \le 20$
• $5 \le n \le 10^6$, $2 \le k \le n$, $N \le 10^6$
• สำหรับทุก $0 \le i<n$ มี $1 \le a_i \le n$

คุณสมบัติพิเศษ A: สำหรับทุก $0 \le i<n$ มี $a_i \le 2$