E. Энгийн мурийлт

хугацааны хязгаарлалт 3 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Тоон цуглуулгын энгийн мурийлт гэдгээр уг цуглуулгын дунджаас медианыг хассан утгыг тэмдэглэе.Танд $n$ ширхэг бүхэл тоо(ялгаатай байх албагүй) өгөгдөв.Тэгвэл хамгийн их энгийн мурийлттай хоосон биш дэд олонлогийг(элемент давтагдан орж болно) олно уу.

Цуглуулгын дундаж гэдэг нь өөрийн элементүүдийнх нь дундаж утгыг хэлэх ба Цуглуулгын медиан гэдэг нь элементүүд нь дараалалд орсон үед голын элементийг хэлэх ба хэрэв цуглуулга нь тэгш тооны элементтэй бол голын 2 элементийн дундаж утгыг хэлнэ.

Оролт

Эхний мөрөнд цуглуулгад байгаа элементийн тоо болох ганц бүхэл тоо $n$ ($1 ≤ n ≤ 200 000$) өгөгдөнө.

2-дахь мөрөнд $n$ ширхэг бүхэл тоо $x_{i}$ ($0 ≤ x_{i} ≤ 1 000 000$)-ууд өгөгдөнө.Энд $x_{i}$-аар цуглуулгын $i$-дахь элементийг тэмдэглэв.

Гаралт

Эхний мөрөнд дэд олонлогийн хэмжээ болох ганц бүхэл тоо $k$-г хэвлэнэ.

2-дахь мөрөнд $k$ ширхэг бүхэл тоо буюу дэд олонлогийн элементүүдийг дурын дарааллаар хэвлэнэ.

Хэрэв олон дэд олонлог хариу болж байвал алийг нь ч хэвлэсэн болно.

Орчуулсан: Баатархүү

Жишээ тэстүүд

Оролт
4
1 2 3 12
Гаралт
3
1 2 12 
Оролт
4
1 1 2 2
Гаралт
3
1 1 2 
Оролт
2
1 2
Гаралт
2
1 2

Тэмдэглэл

Эхний жишээнд оновчтой дэд олонлог нь болох ба, дундаж нь $5$, медиан нь $2$ байна.Иймээс энгийн мурийлт нь $5 - 2 = 3$ болно.

2-дахь жишээнд оновчтой дэд олонлог нь болно. Элемент давтагдан орж болохыг анхаарна уу.

Сүүлийн жишээнд аль ч дэд олонлог нь ижил дундаж болон медиантай тул энгийн мурийлт нь $0$ байх юм.

Сэтгэгдлүүдийг ачааллаж байна...