#80O'rta

Pufaksimon saralash

Vaqt: 1 s · Xotira: 256 MB

Massivlar

Shart

Massivni o'sish tartibida pufaksimon saralash algoritmi bilan saralang: qo'shni elementlarni solishtirib, chapdagisi katta bo'lsa ularni almashtiring; massiv bo'ylab bunday o'tishni $n - 1$ marta takrorlang.

Saralangan massivni va algoritm bajargan almashtirishlar sonini chiqaring.

Kirish formati

Birinchi qatorda $n$ ( $1 \le n \le 1000$ ). Ikkinchi qatorda $n$ ta butun son ( $|a_i| \le 10^9$ ).

Chiqish formati

Birinchi qatorda saralangan massiv. Ikkinchi qatorda almashtirishlar soni.

Namunalar

Kirish

5
4 6 2 1 7

Chiqish

1 2 4 6 7
5

Kirish

3
1 2 3

Chiqish

1 2 3
0

Izoh

Faqat chapdagisi qat'iy katta bo'lganda almashtiring — teng elementlar joyida qoladi, aks holda almashtirishlar soni ortiqcha chiqadi. Birinchi misolda: 1 2 4 6 7, almashtirishlar $5$ ta.

$n = 1000$ da almashtirishlar $\approx 5 \cdot 10^5$ ta — ikki ichma-ich sikl vaqtga sig'adi.

Pufaksimon saralash

Vaqt: 1 s · Xotira: 256 MB

Massivlar

Shart

Saralangan massivni va algoritm bajargan almashtirishlar sonini chiqaring.

Kirish formati

Birinchi qatorda $n$ ( $1 \le n \le 1000$ ). Ikkinchi qatorda $n$ ta butun son ( $|a_i| \le 10^9$ ).

Chiqish formati

Birinchi qatorda saralangan massiv. Ikkinchi qatorda almashtirishlar soni.

Namunalar

Kirish

5
4 6 2 1 7

Chiqish

1 2 4 6 7
5

Kirish

3
1 2 3

Chiqish

1 2 3
0

Izoh

Faqat chapdagisi qat'iy katta bo'lganda almashtiring — teng elementlar joyida qoladi, aks holda almashtirishlar soni ortiqcha chiqadi. Birinchi misolda: 1 2 4 6 7, almashtirishlar $5$ ta.

$n = 1000$ da almashtirishlar $\approx 5 \cdot 10^5$ ta — ikki ichma-ich sikl vaqtga sig'adi.