B. Робин Гүүд

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

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

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

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

Бид бүгд Робин Гүүдийн сэтгэл хөдөлгөм түүхийг мэддэг билээ. Робин Гүүд өөрийн нум сум харвах чадвар болон хурц ухаанаа ашиглан баячуудаас мөнгө хулгайлан ядууст буцааж өгдөг.

Кеколанд-д нийт $n$ ширхэг иргэн байх ба хүн тус бүр $c_{i}$ ширхэг зоостой байв. Өдөр болгон Робин Гүүд хотын хамгийн баян хүнээс яг $1$ ширхэг зоос авах бөгөөд үүнийгээ хамгийн ядуу хүнд (хамгийн баян хүнээс $1$ ширхэг зоос авсны яг дараах хамгийн ядуу хүн) өгөх юм. Сонголт нь цор ганц биш байх тохиолдолд, тэрээр тэдгээрийн дундаас дурын байдлаар сонгоно. Харамсалтай нь Робин Гүүд их хөгширсөн бөгөөд $k$ өдрийн дараа дахин ийм зүйл хийхээ болих юм. Иймд тэрээр эдгээр сүүлийн өдрүүдээ ядуу хүмүүст туслан өнгөрүүлэхээр шийджээ.

Хамгийн баян хүний мөнгийг Робин Гүүд авсны дараа тухайн хүн нь хамгийн ядуу хүн болох боломжтой ба түүнчлэн Робин Гүүд түүнд мөнгийг нь эргүүлэн өгөх ч боломжтой юм. Жишээ нь хэрэв бүх хүмүүс ижил тооны зоостой байвал дараагийн өдөр нь тэд мөн л ижил тооны зоостой байна.

Таны даалгавар бол $k$ өдрийн дараах хамгийн баян хүн болон хамгийн ядуу хүний эд хөрөнгийн зөрүүг олох юм. Хамгийн баян хүмүүс болон хамгийн ядуу хүмүүс дундаас дурын байдлаар сонгох нь хариултад нөлөөлөхгүй болохыг анхаарна уу.

Оролт

Эхний мөрөнд Кеколанд-ын иргэдийн тоо болон Робин Гүүд уг ажлаа хийхээ болих хүртэл үлдсэн өдрийн тоог илэрхийлэх 2 бүхэл тоо $n$ болон $k$ ($1 ≤ n ≤ 500 000, 0 ≤ k ≤ 10^{9}$) өгөгдөнө.

2-дахь мөрөнд $n$ ширхэг бүхэл тоо өгөгдөх ба эдгээрийн $i$-дахь нь хотын $i$-дахь хүний анхны эд хөрөнгийг илэрхийлэх $c_{i}$ ($1 ≤ c_{i} ≤ 10^{9}$) байх юм.

Гаралт

Дан мөрөнд хамгийн баян хүн болон хамгийн ядуу хүний эд хөрөнгийн зөрүүг хэвлэнэ үү.

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

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

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

Тэмдэглэл

Эхний жишээнд нэг өдөрт хүмүүсийн эд хөрөнгө хэрхэн өөрчлөгдсөнийг харцгаая.

  1. $[1, 1, 4, 2]$
  2. $[2, 1, 3, 2]$ эсвэл $[1, 2, 3, 2]$

Иймд хариулт нь $3 - 1 = 2$ байна.

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

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