Сколько сэкономил Флойд
В ядре Linux сравнение двух элементов при сортировке — вызов функции по указателю, и каждый такой вызов дорог. Поэтому в 2019 году пирамидальную сортировку ядра перевели на просеивание снизу вверх. Проверим выигрыш сами: отсортируйте массив по возрастанию двумя вариантами пирамидальной сортировки и посчитайте, сколько сравнений элементов сделал каждый.
Оба варианта одинаковы во всём, кроме просеивания. Куча — с наибольшим наверху, в массиве a[0..n−1], дети ячейки i — 2i + 1 и 2i + 2. Сначала для i = ⌊n/2⌋ − 1, …, 0 просеивается ячейка i в куче a[0..n−1]. Потом для e = n − 1, …, 1: a[0] меняется с a[e], и просеивается ячейка 0 в куче a[0..e−1]. Сравнение — это одна проверка «меньше ли x, чем y» для двух элементов массива.
Обычное просеивание ячейки r в куче из m ячеек. Пока у r есть дети: если детей двое, сравнить левого с правым (a[2r+1] < a[2r+2]) и выбрать правого, только если левый меньше, иначе левого; если ребёнок один, выбрать его без сравнения. Затем сравнить a[r] < a[c] для выбранного ребёнка c: если нет — остановиться, если да — поменять их местами и продолжить с r = c.
Просеивание снизу вверх ячейки r. Шаг 1: начиная с j = r, пока у j двое детей, сравнить левого с правым так же и перейти к выбранному; если после этого у j есть один ребёнок, перейти к нему без сравнения. Шаг 2: пусть x = a[r]; пока j ≠ r, сравнить x < a[j]: если да — остановиться, если нет — перейти к родителю j. Шаг 3: элементы пути от r до j, кроме самого r, сдвигаются на этаж вверх, а x встаёт в ячейку j.
Первый пример можно проверить вручную. Второй — настоящая фотография из статьи о пирамидальной сортировке: яркости 9600 пикселей, строка за строкой.
Вход
В первой строке n (1 ≤ n ≤ 20 000), во второй — n целых чисел от 0 до 109. Числа могут повторяться.
Выход
Два числа через пробел: сколько сравнений сделала сортировка с обычным просеиванием и сколько — с просеиванием снизу вверх.
Примеры
Пример 1
6 7 1 8 2 9 3
15 14
Пример 2
9600 91217 93691 100959 114309 113113 92186 94339 85381 78815 86463 85360 88638 85246 77772 82659 87845 87845 92297 94205 115327 137857 156174 159832 168159 180611 188753 191112 193710 193596 195585 200368 195770 191585 192471 194656 188514 182073 177828 174589 184030 192286 193471 185916 165436 144059 122486 102973 101375 101375 101261 101386 103272 101261 100973 99859 98848 103158 107539 108425 110496 107528 106642 105528 106941 111724 114322 117404 120774 120763 124073 123671 138792 157696 136721 125970 130052 145358 167991 163290 149322 147137 150322 161589 184998 203798 204097 180258 156006 153924 152853 167045 163159 152120 154120 155305 157120 159903 164387 169757 175426 181084 183383 187280 189639 193123 197194 200852 202325 204553 207336 209336 209923 209695 210581 210880 210581 211467 212652 213239 208869 86526 91011 95371 97866 93485 84299 81288 86289 100525 82153 83762 88453 94927 90133 94710 100700 89927 86905 88101 90998 105212 123611 131177 143711 165088 180013 192112 196183 195183 193884 197069 200254 197841 197841 199727 204912 197069 187514 178660 182030 191172 195058 184731 161767 129927 117404 108642 101848 102745 103745 104745 105044 104229 106528 106941 106827 108838 114692 114920 114208 110724 111795 112496 110126 111126 113909 115806 116991 117991 121774 128340 141162 143287 134422 136906 146543 148685 148653 148610 139767 138881 142354 150208 176628 199912 193656 169518 152152 153223 162230 182813 188482 168600 156849 159148 161561 169643 175127 179312 184155 190824 195297 198080 199966 201852 204738 206450 208809 209108 207809 208809 209809 210108 210581 210581 210581 212353 212239 211353 209869 86412 84423 83021 87908 81391 79516 79402 86887 134214 109276 78957 82153 82349 88535 99091 94792 91297 81616 81018 85019 92678 99244 104212 118056 140042 149668 167447 180671 185742 185041 185628 189112 194368 200026 206385 210869 204499 192944 185802 183215 184916 181546 161468 136123 115795 108115 108827 107229 106044 106642 108941 110126 109425 110838 111724 111724 113735 117817 118589 116219 113621 114621 114208 111909 110713 109300 112909 119176 122247 124970 135906 159539 159724 159550 158148 151180 141685 142055 145468 136756 133571 130386 137468 155920 175916 167991 154294 158077 156849 162301 178514 191368 179927 164301 162529 168828 178970 185454 190710 195781 198667 200439 201553 201966 205151 206923 208222 208809 208624 205923 205211 206097 207396 207396 206983 208695 209282 209168 208467 206869 86722 88299 90392 83804 82103 101041 91855 83153 107483 116462 83338 82039 84246 83730 85638 87008 89090 83214 79007 83410 93091 98059 100130 107707 113273 118714 129177 144885 165849 175301 178372 180785 185443 194471 204499 204613 204499 199841 189873 182617 176290 164137 149831 124774 115795 116208 110240 114023 112724 111425 109827 113311 112909 113735 117578 116208 114735 114621 115507 118877 117692 114909 115023 114322 114909 113610 113023 118578 123361 128742 135781 164208 178204 184987 178503 171361 154137 146642 146941 143055 135973 129190 138870 154436 166475 163632 159621 166703 159219 153034 169372 182411 176041 168372 174856 187525 191183 195254 197553 200852 201966 202738 203624 205624 207923 207222 206809 207108 207325 207037 206037 205325 204325 197738 198211 203097 203510 204396 204581 202869 94876 96279 96339 88865 88773 107401 122441 112266 117131 117544 96101 83719 83246 84029 84638 85410 82203 79719 86204 91482 89297 94749 99315 95347 93624 102913 118953 122508 138689 165148 178258 178073 178959 184916 195357 200026 201086 205684 202727 191172 181247 168920 160767 141265 139792 126258 109528 113496 113610 114610 113724 120578 120763 115507 120176 118279 116692 118877 118991 120176 117279 115980 118578 118578 118279 120176 125546 129329 132699 138781 140461 160909 174535 178133 179204 180389 165350 148642 146272 147756 143386 142717 152169 159137 162322 164692 162692 162991 161817 158105 163475 169486 170372 182329 192482 193482 198727 201325 202325 203798 204097 205211 205211 206108 206222 205923 206097 206695 204738 203738 202738 200325 198439 196738 199624 203097 203396 203983 203755 203282 99339 96866 96339 100041 104618 110668 116946 109380 131676 135758 103874 88535 84317 81534 81719 81904 79594 77996 79007 91781 95048 90069 90955 91428 92542 90830 98891 114746 132134 146543 155881 163550 170703 180443 190172 197314 202499 205271 203684 197243 188688 177475 166023 160055 147347 125247 113784 111713 114300 115012 115610 120464 124834 125247 123535 121649 122948 125845 128030 125133 123834 124546 129329 129340 129927 135770 137596 137297 137183 138770 139080 145119 148261 145717 152642 160795 160980 151941 148201 154799 158066 162137 172692 173877 176176 173062 165578 175486 183742 179030 177731 181628 190297 196955 197955 198727 203097 204097 204097 203510 203097 203097 202439 201510 201325 201738 201738 201097 200738 198553 196852 196738 195738 198325 202097 203282 203755 204456 205168 204581 101421 96339 95638 96236 97019 103792 106885 102504 111451 114234 104358 97205 89905 84513 85709 87976 87204 85008 81975 80975 83367 87161 83242 83655 90542 90428 89058 97407 115817 127166 138689 152696 161550 172589 183030 188286 194243 199200 202570 199314 187389 179834 175290 169208 149891 126546 119866 117382 117197 115898 114898 116382 120937 124535 125834 127133 126731 129916 130030 127617 129802 132699 135411 135884 136770 138183 136411 137585 136058 134884 135400 138667 142222 141336 145902 151044 159012 158425 166197 175279 178176 179959 183731 186204 189090 188503 188101 192873 193172 193243 194656 198140 200912 198912 199613 200613 202097 201097 200211 198738 198325 197613 196553 194667 195667 196966 196966 196738 196738 195738 195738 197738 200097 201983 203396 203994 204581 205467 205239 203467 100720 98008 95410 95111 93111 91627 94019 94318 91307 91133 89421 91090 89133 86894 88688 91297 90297 84552 84367 85976 83954 82356 80932 83840 90955 97005 98902 98592 101489 108653 123845 135379 148728 159539 168692 178432 182802 189172 193830 184389 175350 174393 174991 170208 149005 128432 123937 124948 124361 123763 120752 120165 121350 123236 126019 129802 132987 133286 134884 136656 137656 137667 139852 142439 137955 137770 136357 133873 133574 136058 139069 145222 149663 154261 158240 164012 169496 172578 175877 178475 180361 182247 183318 185503 187503 189389 192460 194172 194357 194243 195357 197428 197841 196841 196727 195254 197912 196912 195140 196254 197140 196439 195667 195966 196439 196325 197325 199325 199211 199923 202108 204695 205581 205581 205467 205766 205065 203364 201951 199951 103101 100204 97720 96008 93709 92997 92410 90111 88812 89410 90894 86100 84502 84100 85780 87802 92080 89286 83666 84666 86748 84666 83242 83851 92738 101098 98788 102272 100190 99652 107827 120660 136265 147016 158066 164507 168866 174763 175649 168208 167795 168496 167610 156560 133101 130019 129019 129019 130617 132802 130204 126720 127307 127307 129503 130677 131688 135297 140140 146222 148293 147592 149891 149005 149592 146222 145923 143325 144037 147706 151777 156446 159930 165713 168784 169784 171969 175165 176578 177763 179948 181834 183019 185802 187503 188976 191275 193759 194243 194243 193058 191759 193770 193770 192357 193183 192183 191770 192542 193542 194140 194553 193553 195439 197624 199396 202581 204880 205467 205478 207065 207538 207951 207951 207538 206538 205837 203250 200837 201837 106895 104172 101873 100400 98389 95079 93008 91410 89698 89883 88883 86698 85997 89987 98760 92667 91482 87574 87460 87460 84851 83726 98717 96233 92510 105767 107550 104941 108425 109425 109724 114393 125329 134667 144119 149087 153272 158343 162126 162827 163126 163186 161528 140955 134987 138770 137884 135172 135172 135286 133275 130905 132275 133873 133987 132275 133873 137069 141624 154973 163414 167083 177236 177122 170268 169382 167311 156446 156446 162115 161229 166898 172567 171567 172567 173567 176350 179535 179937 180535 182133 185090 186204 188389 188389 187688 188862 190460 192645 191759 190172 190585 192357 190585 189286 190884 191770 190183 189884 189770 190069 193841 199211 202168 205880 207065 206951 207364 208136 207837 208837 208723 208609 208723 208609 206723 206609 205310 202837 208908 109390 105493 102884 100884 100297 98286 96101 94389 91492 89709 89481 89965 93770 109120 107305 96760 87987 84552 85161 90841 88232 86645 99799 100500 88890 95168 104941 102457 105941 113507 110610 118062 122258 125916 130585 135368 144820 151973 149603 148706 151788 153375 155087 145624 141428 140542 139656 137770 136471 135574 135286 136471 142140 141841 139841 140841 141026 144510 158229 163898 160115 170154 173638 173524 177122 176823 168670 165599 168556 169556 171154 178535 179720 175823 178122 180720 179834 180606 180421 181606 184204 187389 188275 188862 187862 190058 191232 190933 193645 191759 189574 190286 192357 191656 190884 192183 194553 197026 198026 198325 202097 206239 209723 211609 210723 209723 209022 208837 209723 210609 210908 210609 210495 209908 209495 208609 203723 207609 209908 178097 120821 113255 107162 105564 103564 102493 101678 98080 102173 102347 91873 89275 90161 103255 102326 100614 94037 84965 84976 85150 89841 99500 105952 98190 89613 88890 92086 94168 101446 108425 108012 111083 115578 121247 123845 126617 132770 138553 136656 133873 136955 142325 139841 134058 140325 142325 139656 135574 136172 139944 144798 147396 152478 149467 145211 144624 142510 153261 169866 181492 170040 165670 168268 175823 174823 172339 173339 175638 175823 177709 180307 182503 183492 183791 183905 184791 184791 182791 183791 184677 186976 187275 186976 186976 192531 201499 202086 200385 201385 202684 199200 195129 191357 190656 193243 193841 197624 204456 207940 208239 210011 211495 212196 211609 211495 211495 211495 211082 211609 211794 212979 212979 212392 211979 211093 207794 215865 204424 114937 67620 121006 117212 112141 107059 103564 103390 104760 105244 113131 120295 126850 116746 97760 98543 108490 103696 100500 90841 88058 87047 96005 110746 109920 101571 91983 93983 92271 95880 107610 124753 114991 110795 116877 119062 123318 124916 127514 132058 131699 131101 133172 134346 134357 172268 205374 202189 178040 154777 164403 155549 162517 159446 156147 157734 149880 146695 157631 173524 172524 177421 172524 167855 173339 174410 173709 180606 179008 176296 177421 182976 185161 188047 191645 192531 190933 189047 187862 186976 186862 185862 186161 188161 189047 193830 201271 204744 204570 205755 208228 210641 211228 208755 203869 203271 201858 199684 204168 208239 209125 210897 211196 212082 213566 213566 213680 213979 215637 214751 213751 214050 213164 213751 213751 212164 207979 216050 182353 93268 51641 60940 120408 117995 118006 127355 117718 104461 102048 99265 106027 113903 126334 137455 129003 127003 129900 128074 116540 101696 106593 95005 93407 99674 102457 100859 97364 99076 91385 95467 101332 108909 110980 111382 115763 118834 119133 120133 122193 123606 124720 129389 131275 129574 169154 214196 222441 231811 228925 217299 212228 190449 171257 169958 181709 162588 155147 163300 172752 175008 176894 178193 178307 173823 171926 171638 173823 174709 175410 176008 180492 187449 189933 191232 195477 195890 194004 189933 187862 188862 189460 189346 190944 194716 196488 197787 199271 200858 202570 204755 208641 212114 211712 210712 209826 210712 209712 209826 209712 209712 212484 212783 212968 214566 216039 216050 216936 217708 217708 217132 217121 216121 215534 214235 212936 209751 219007 198848 78311 57392 81627 70175 119707 117995 115810 126583 137715 132035 126252 119572 103532 100532 106522 119839 136754 134042 132042 136124 127960 122693 129857 121693 114415 103055 94478 95065 98364 94581 93570 98065 102816 105300 106898 107012 110382 112567 112866 116279 117464 116937 120410 125791 127976 138912 165752 187303 206712 216669 224213 218740 214598 211000 211413 211815 223441 202776 164474 171926 174410 176307 179492 180378 180378 176122 171040 169040 171709 177008 183264 187933 193004 193890 194776 196075 196673 196559 196673 195488 193075 193303 195673 195488 195189 196787 197972 199673 201858 204157 206043 209228 210299 211185 214484 214897 212783 209598 210424 211011 211897 212669 213267 213680 215637 217708 218121 217420 217420 217420 217420 217719 217719 215605 214605 218491 221377 218534 198207 100464 58033 73556 108314 82997 131366 123974 119479 118191 119501 123469 132519 141754 130633 110593 105098 114159 132373 139309 137537 140195 138793 140206 130330 120693 120981 122465 123878 112404 112290 110692 100033 102517 104599 107311 108197 107599 107898 109969 111567 113866 115165 117823 122307 125791 130873 136841 140396 156670 177460 195271 206886 207886 207299 206000 205712 204299 204701 209185 189531 179079 182563 182449 180563 179378 179563 173595 172524 176894 183748 188819 190716 194374 196559 196146 195260 196559 198157 197858 197858 201342 202929 201456 199630 196385 195972 197271 202157 202342 203157 203929 208701 207114 204000 209783 212669 215153 215452 208196 206897 211669 210968 208968 213751 216121 216306 218007 218192 218306 219306 218605 218605 216132 215616 219801 221089 198381 165634 137176 72517 60392 76040 76638 84791 72100 136334 131551 124159 119974 119974 117974 120583 125024 127220 126220 120725 111675 111561 131145 149060 154914 146060 137782 125248 117383 108920 117856 134586 132401 125020 121938 114589 110393 109382 112464 113464 110855 114350 117720 117133 121090 122802 125688 127286 131058 134841 137325 143136 150186 156442 171036 184673 202598 212370 203174 206000 211484 208071 205772 202886 198157 189118 184036 180378 179378 179264 181563 183460 187531 191189 195445 203342 205114 200929 202228 204228 205228 201815 197744 197559 202815 205228 205527 204516 203228 203641 202755 199869 199641 205413 213484 212071 193456 196527 205669 210039 207039 211050 215306 211409 210338 212697 209637 205637 212306 217491 218964 219850 219263 216964 213192 210605 219089 218676 191424 144649 104863 90329 63549 63773 67773 63463 68306 72481 60448 124675 123860 122860 123757 129323 131334 131704 131889 146010 147793 142423 130960 118426 117312 124166 131444 134412 136597 137896 134999 126020 116671 128020 141027 136059 123052 124237 120628 119742 118144 116247 119133 121987 125770 129069 130553 131026 132026 134439 136510 138396 140581 142136 147702 154659 164296 175150 171221 137274 104327 130064 177783 181135 191402 209359 220512 208598 192819 192819 192890 191189 189303 193673 200342 204239 202826 172395 170107 194570 188847 184961 181260 201701 210712 206413 202114 205000 197516 193744 198445 204413 197641 182901 193157 185776 153100 125257 136421 136008 164933 150182 145161 150666 145687 164776 199452 216491 218790 216904 216676 213975 215448 213676 211089 208377 210377 210904 174200 141122 106717 104607 97069 71734 62876 68648 67545 60061 58263 61345 48007 123148 121077 120077 120561 123643 127323 128209 136672 149092 146978 138341 131373 123280 122095 122095 118383 120568 123351 138369 148718 145935 136657 128493 127020 126906 124123 128080 129379 126009 124710 126596 129667 135521 138304 140304 139304 138592 141777 142364 141663 147261 151136 153805 161040 162627 144246 113153 96110 94431 89566 118559 121897 114754 114829 152374 192473 210142 188733 188772 209811 213452 200744 192488 175993 161356 115854 85662 99267 109306 106648 106534 105246 121182 144079 189374 191972 196043 197043 195342 197527 171036 115000 92292 119050 93509 83449 105816 109382 97538 104446 90944 101108 110517 101809 101983 115267 138246 178342 183185 190968 222160 218160 218160 217160 214160 205676 156944 111571 117055 114407 92581 65452 60349 62164 63719 64459 58057 53046 56231 60487 123088 122974 121148 119963 119376 118034 120045 124312 129063 134031 127063 119611 116301 118198 119796 118383 121166 114301 120938 132700 135184 135657 130390 127020 129678 131863 132048 134646 134760 133048 136347 140902 143984 149240 150126 148528 147941 150528 152001 153332 143919 135534 133442 123417 129630 112993 111363 125886 114217 119755 124228 131751 129626 120092 108737 110025 128694 109698 109047 126847 141630 142064 118459 91897 77797 79868 81982 87434 95441 115481 103463 99332 107866 101257 114143 116121 115865 167531 165612 124669 81758 83449 90613 95940 86683 95858 102930 102435 102538 115197 119083 113631 108663 114631 114196 100417 96346 107168 133791 148445 181768 191160 188932 181758 172345 152196 124638 121631 113891 93321 69687 66203 59865 69573 70954 54128 55313 59199 58085 51715 131312 124518 122931 123344 123045 122045 121828 120714 123209 125579 127949 127949 127949 128134 129618 130629 130330 130390 131102 130689 128504 129977 129276 128977 131450 132934 134646 136945 139016 142272 144457 145343 146642 149012 151909 155496 158311 158126 154599 119463 105541 114929 110417 113314 115755 120267 129491 118185 123854 126480 122555 131121 129306 122544 121174 112292 105541 109840 103986 102698 113292 111053 117961 108758 81053 86320 91125 88011 110210 113737 102235 100403 108464 109926 107855 105556 92652 89755 84765 74448 85623 93282 101631 99321 90260 107012 104115 102859 112969 119165 119279 137172 120980 118300 113033 111022 109239 113136 123485 141890 146658 153110 151028 145804 133498 120278 129132 105431 79616 69214 69812 69100 69128 67395 59025 55199 52416 51302 55199 52715 167202 166974 134291 123643 123942 122529 122643 130209 129878 127237 124639 125650 127422 127134 125536 133401 133113 136358 136141 132945 134358 134358 134532 136016 134532 134945 137016 138902 142272 144756 145229 143930 144343 149941 157023 154795 135122 129335 126516 102053 112303 124940 112417 111346 112172 116744 126192 115740 115456 122626 118826 122968 129377 99395 127697 132078 110477 103943 101747 106438 115520 113993 110737 112922 86843 79907 96648 105541 104057 108182 104100 96947 107171 107698 111122 107442 107556 98495 94000 88548 84178 88456 96620 88826 100093 105257 100566 91054 103403 116339 127916 131275 136232 129791 118795 128606 111990 130834 107136 130193 124154 122915 145662 124616 114125 113723 94790 73285 67171 68100 67502 67128 59993 53438 53797 53797 55683 53683 52199 46943 139732 148070 136721 127084 125198 125714 122884 111164 119852 128351 133031 132803 127308 123938 123639 126308 126721 129091 135244 138554 138141 138913 140500 141098 142169 142283 143457 141571 141158 142044 146457 147859 150859 139702 123812 110427 111527 116566 121719 124605 121854 129299 112548 104232 109374 111456 119669 111430 111647 130594 119555 118370 113288 93373 122953 128508 131263 115587 107455 106683 111004 107922 111395 119815 111836 77174 98687 105324 110737 94719 87936 105128 93904 99698 105421 103502 98719 98349 100534 79537 91609 95566 90424 91723 96153 92196 95506 90826 108784 124389 125998 133015 119769 125965 136118 135531 119111 126780 135819 125296 107805 114061 110865 119773 107218 85171 76797 77851 67573 65986 63427 60053 54580 57053 56053 51085 50797 52580 46014 41470 135052 131867 132753 133237 133052 117523 93588 90539 104231 131084 129020 132803 131618 128906 128009 129205 130390 134059 137956 137842 135956 134059 134646 139386 141528 143756 142756 141870 159393 166948 138083 139933 129929 116342 107559 97922 121783 117082 121306 134302 130149 125441 116342 113701 110260 122783 119740 113800 125295 118327 119224 118284 93341 108989 124682 119611 123551 122768 116832 108135 110847 105879 106737 107808 103270 93132 96111 110406 105694 74060 83637 104840 101285 98057 102584 96502 102345 93822 96833 89854 81516 91794 98246 91979 90196 106812 102616 107627 123460 120905 125161 139755 124922 123965 124264 142097 147413 113328 131047 115638 105876 118328 107577 93616 78769 73840 79623 67171 66057 67466 54281 54640 54825 52167 51879 47096 40356 49281 51569 54950 139906 142547 139906 140237 129489 106401 87599 83199 95031 110820 131639 131248 133504 133265 131678 132689 137532 142511 140799 138315 136315 140913 148642 142158 141272 143713 146941 146571 143720 132641 112213 116480 116904 118637 110114 109972 120239 112125 121078 135949 150846 130523 116652 120968 111413 117398 123067 121850 119562 117437 121551 100163 119252 116882 123394 116753 115084 119654 114772 118772 111804 108032 105776 100683 88964 90203 110890 103591 90106 74832 85893 96715 98014 89850 89779 92274 106651 102313 94078 111808 90007 77929 99089 82245 97844 112791 107943 114851 120520 121993 114253 127776 132434 139043 136043 135983 135260 137630 139641 134417 116079 117068 90595 68943 70943 72954 65459 66644 64466 52879 53466 50879 48982 41427 44911 49064 41726 50053 50754 51352 140027 138446 127186 142272 110201 103586 78233 72676 65607 87788 124491 129037 132009 133080 132781 133080 135336 140016 141212 143169 150322 155991 175357 163546 148539 156838 144773 121473 119263 112719 120377 122121 120039 118854 103032 107630 117626 113284 124562 126747 141672 135704 122497 132953 120290 114714 121747 124900 126373 127046 119024 122448 130530 120740 124463 122035 121003 120807 110686 115615 121142 110647 104092 101939 76871 102270 112135 85633 78170 72615 79942 82426 87487 102124 96726 91231 92932 94117 95872 106911 108509 90175 103666 93491 111563 110851 104356 107644 128516 130929 121178 127488 132331 129929 136897 137256 124064 134331 138886 129331 90352 101821 98288 70427 72427 70612 70281 65793 56434 48281 52053 44210 46384 40199 40911 50722 47352 49836 48352 46167 118896 129526 125270 151328 75874 87803 65930 55702 59502 84517 108887 128289 137482 135080 134656 134254 135738 136553 139564 144418 148158 148283 147055 155126 149702 125947 121484 117900 110142 112213 116665 104854 118280 120796 119779 110686 111757 114329 117209 125052 107664 118904 119280 117186 105794 105827 109860 115110 109914 103799 102685 104647 117463 113740 113121 118566 126665 121078 118491 116665 117882 113957 101206 95928 94455 97683 91259 88889 74284 80334 86693 79611 97320 107288 107086 104694 86149 93840 94139 97655 109705 102666 93573 99356 117602 112292 115651 109025 123043 124619 131886 128402 129271 130755 134125 131114 131658 130505 107950 83238 89576 111665 99598 69128 69726 69950 62978 56978 54380 50021 51021 47053 43569 49423 45580 45537 45651 45765 51320 50619 111027 111240 108872 102775 63261 77235 60061 53246 59388 57975 78104 137459 148020 142336 140325 141667 143368 139549 141670 141752 145627 146072 150560 121534 110455 100675 122188 99565 94739 118394 112579 105514 117695 117585 113856 117035 118508 113742 112198 91586 95581 101772 103723 101011 101598 108414 103332 101261 91059 83895 88140 87781 103576 108327 108843 98494 99526 84917 99941 105931 112708 105060 100750 105060 93444 89960 87672 91939 90281 88156 78568 76736 98619 105288 93189 99434 103765 92128 85530 96666 101477 117516 107765 103324 120260 116146 112651 115836 121565 122565 124875 122989 124174 125701 134228 121559 130957 109918 79053 76868 94940 89804 72210 67395 71049 63049 51434 53206 42455 46651 49206 41754 42053 45135 44178 44537 44064 42466 46836 51206 124569 79812 94111 68831 52831 48016 44956 37956 43913 50218 68289 105216 134672 158347 157891 153816 137075 122504 119618 118270 120971 115785 125828 109013 118102 123113 100974 116297 123401 125113 111809 106946 109017 114630 115955 119693 121063 112198 90532 77927 105289 108866 101495 105914 103800 107392 112767 105799 98136 99354 89358 83069 104870 105006 84846 82792 93468 99806 101535 111656 106796 108110 102049 105903 99451 88433 97679 95793 82672 90782 91270 82878 95266 95505 92722 93896 96320 99363 97395 94025 85943 106879 126566 116804 110825 117804 115277 116967 113244 112358 124761 129256 126185 126946 126604 126761 105918 79836 79950 80537 89103 72466 66124 67522 61647 57935 43167 48434 44053 46124 46608 43537 42363 40950 44619 52163 46548 44249 44423 44537 88762 82756 92612 71085 45356 32709 50395 28498 40227 46674 53016 67560 139885 172571 147125 129526 119842 128163 125070 123184 134989 116618 116977 120162 123842 113618 123027 131636 118390 108955 102462 92072 99610 106522 112129 126863 113024 99702 99218 111741 112606 111937 104235 102110 96267 109773 116387 96403 93620 95631 93973 87065 102664 117202 80906 94251 101187 85326 89462 98518 102916 110368 110600 100277 110615 85885 99832 76590 90782 97152 79867 91629 100826 90494 78454 72611 100000 101718 100380 104879 91932 72637 109537 115391 114619 112565 123159 119120 114597 123587 126783 124669 124712 127783 129996 106946 75569 83548 82146 76352 68793 67707 57875 57935 52505 50505 41466 43537 47793 44135 42309 43320 43320 48576 41722 42505 45320 38167 43434 41548 55334 84332 120584 76954 50111 52726 53586 33438 37526 61672 59760 72814 145174 134519 125369 125728 124298 122244 129049 117472 126500 125266 132978 125059 118054 129913 132668 123412 129913 114310 88522 70115 71001 81192 117587 139229 103176 111578 129759 122396 114090 115535 103551 101067 94474 110230 93756 89805 92332 90033 88033 100991 117437 111273 92909 87408 87870 73792 82244 78831 90724 94550 100486 98301 116708 114355 81586 83341 87999 73796 87423 97320 97548 87395 64273 82618 96516 101245 103729 104903 119701 101552 74181 80149 114092 124441 115305 113206 129669 123598 123370 120783 121011 122886 105103 73395 75053 78537 72722 65049 60761 60419 51206 49793 47907 47793 43548 39167 40423 42021 44266 44565 49348 48277 37053 32167 38249 38434 46576 38124 52175 56229 79218 62173 58111 49797 53386 48315 41412 65885 56156 53608 136799 132668 126401 129440 126266 113205 124087 141126 130386 126913 133223 118472 120386 125315 132814 133939 138027 128136 68212 58446 56674 81186 119854 108707 105580 128705 114727 114450 110868 108161 98007 105644 101421 107400 92311 91827 83603 92061 104909 125861 122682 96208 90425 92001 84424 83315 74885 86593 95643 96067 90669 100252 102938 120551 100544 73938 78949 86651 90929 88135 74063 71921 77949 95533 92907 95163 105099 113796 111600 128327 111178 81519 94569 107135 125523 110288 110804 107847 122555 122783 113733 96021 76352 77836 77978 71636 68479 58821 56935 53462 54049 48081 48391 45576 45505 37694 36765 40907 45092 44103 47348 34363 29808 36950 37135 46163 42989 32363 63736 66274 70878 63489 60743 51945 55545 56044 40868 44842 54608 100099 124958 135507 132315 131027 135696 127913 132685 140343 139055 137810 133326 125038 125038 130571 125891 121553 106825 93059 81571 53332 57093 85485 94186 83355 98609 97970 93643 95817 104911 117777 106585 115325 121809 110439 109759 103584 96584 100655 127622 110404 87691 91012 79407 74254 86495 87517 88963 101138 119003 96170 90045 85436 87404 97497 105540 83255 85113 97815 88331 90146 75248 74536 84434 91331 93989 99131 96821 103985 117280 116383 124099 93612 79633 95352 127768 132725 120985 109821 103608 112832 93081 76825 76249 74778 64892 59522 75100 63425 47804 45021 49864 45494 38836 44978 42679 42733 45505 43864 46989 41918 44234 67084 65600 46935 43864 42875 37804 36744 50033 64263 77667 71708 64594 68525 65106 52386 44016 55104 67012 75068 90987 123356 132283 140767 146838 132913 134816 133272 124272 121261 135767 125870 125799 126386 122495 129331 90080 66842 70984 50261 52603 69745 75110 69768 83142 94977 107787 100851 105580 112239 116575 122347 109417 107253 105036 98905 116454 123519 101838 78239 77880 75293 71564 83158 87691 82147 107106 100551 105437 95398 85724 85795 86578 93013 96953 99518 88109 85494 92548 84053 72547 92092 92391 90103 88690 88750 101735 103219 111366 114768 119252 124153 110359 109729 123708 118626 136551 123615 86341 83010 79380 75853 67793 63251 62251 64436 64436 49337 50348 43309 45092 43793 33939 43864 46049 46875 48348 39690 48120 50718 61056 76497 69312 49191 46245 42761 36505 42174 45603 49332 57822 57594 49734 56719 64394 57730 59203 65240 43081 59083 106568 128887 121235 135029 131354 125685 142311 121261 120581 119119 126631 121642 131642 126489 130207 103597 107690 80892 60266 48842 51375 56033 71708 65594 72850 98339 122474 110570 110157 112712 132304 129379 90524 94154 97161 115422 142726 105703 75902 77489 71842 79272 90045 93817 73478 90561 96822 89811 94583 91985 79582 75098 66543 89122 95383 97697 99757 86348 75145 68362 78977 72672 71134 84717 77629 82657 91995 107546 111301 106518 106871 110632 122170 118800 109088 118910 106088 87412 78668 78294 73664 67322 63778 66496 65507 56914 51946 46864 46750 43380 40793 48522 41793 40266 43750 37793 41163 45234 45832 51832 52088 48658 44815 39288 40701 42234 42234 50191 40999 38515 37689 39700 40842 50332 51104 48289 54485 86088 41238 55582 92307 98795 89268 116719 143023 143464 130354 112260 110716 114923 118559 120097 114385 135874 128385 96728 88881 60500 60255 56799 52304 68147 59446 52734 67474 105860 112000 109516 113435 113854 124592 96475 95204 88105 107981 132840 105839 73147 76973 70614 76033 83164 100503 83001 90931 105334 100377 97138 82849 85072 70842 62216 75055 92389 94400 98525 102807 94942 87636 73999 60611 65753 70422 74009 71063 77031 73373 84668 86554 106546 110019 103735 104219 117643 94152 123753 88679 77255 69066 65795 61365 56419 65094 66980 59735 48821 45163 45163 40793 38494 41978 44821 38092 42163 41163 43935 43821 43533 44413 49957 53447 53017 42886 38402 39875 39174 43006 45892 50238 34096 28851 44956 51158 39760 45087 42717 45842 85165 62730 51283 76345 66816 89621 121669 126065 132941 114695 134510 122190 114211 113232 128456 127162 129689 109647 122463 64700 54184 49782 46668 47999 55070 47201 54386 67158 103447 108544 120104 130528 122848 104753 93742 116261 110706 139238 121558 80474 74087 73810 79664 86306 82403 72261 86909 107818 98437 102878 85208 73022 72631 64173 75169 73995 93927 88378 94927 99297 101226 86735 107110 62693 55241 67775 71672 64921 68220 67704 69601 73281 99181 106568 110144 111329 105133 95778 82739 76311 71094 58778 66692 64344 54479 67986 55838 57126 56414 44864 41978 36896 39967 44636 40451 28939 41636 39750 39462 42647 46120 54974 60899 52436 52251 36587 37761 35576 40821 31402 39821 55489 43472 34683 30313 36042 41173 41184 41130 42788 67246 44429 54403 81283 58668 68756 104619 114400 112656 134538 151599 109075 113015 110488 91492 107987 121505 111458 90675 67565 53167 48836 45255 47010 50466 43130 67941 79599 87240 115968 144778 137255 138924 136849 125083 110147 132326 138782 100520 84904 85649 90731 91546 83219 87845 89084 98807 100562 91127 80795 67239 71489 70554 72272 68902 81034 90731 86410 94243 96998 108325 103809 106536 85984 63878 56024 64220 63220 67476 73743 72857 94512 102437 96366 99757 111628 92664 78881 68126 64692 63094 69638 63877 62529 65165 66812 48881 49995 47636 41049 36608 34608 39750 36565 38163 32907 39636 37277 30135 36690 44707 50735 56871 35462 41180 40120 35049 32277 41180 39120 45767 39401 38102 35025 25481 35569 43956 38401 39358 46321 38760 40717 64394 68149 34541 39270 82653 82726 76724 120277 126310 81111 70029 72472 59969 74556 97640 88934 77347 83266 51156 44526 47722 47184 32666 46298 52842 63941 93561 122973 126119 117869 143565 123212 101233 125913 139739 138660 109848 116425 106837 91933 94286 100140 81752 89802 96693 93736 74501 77735 71386 73941 94514 78991 79387 96650 94112 82236 91645 100635 105667 110364 104777 99585 94133 74244 70928 84604 59818 64416 71928 92572 85419 76021 72939 92262 77724 63681 50419 54305 58849 61877 56724 48348 51778 56849 42462 41451 46408 38337 45995 41049 32619 33864 45066 49778 40821 37038 27733 41935 34576 34163 43479 33163 34761 42778 34462 35761 40006 38294 41066 24410 23769 28535 22051 33139 43657 39657 38586 36042 36988 45261 56078 51648 25769 29182 62728 86939 92791 79388 91954 102585 84036 39287 66173 94352 100032 86874 66364 50575 34139 40569 39249 33683 35395 56642 59881 75240 116663 118440 132799 149522 134391 114653 108635 137298 145632 143716 116257 116274 118872 115719 92748 76556 82535 82834 89269 90497 77105 87318 74012 91275 85606 74980 99547 88280 90166 101710 88948 76937 94069 99075 95428 99471 107069 102303 104787 107994 98585 72184 62487 86746 80533 78337 70337 71365 61909 57909 56262 54849 50892 49120 52066 46821 44821 47707 44522 39636 39522 41109 40636 34565 32793 41707 42006 41533 37223 38109 40120 42892 42767 35049 36832 36120 34288 39305 37718 41305 34761 34636 39066 35139 37210 28062 27552 33797 31313 51218 44261 33085 37988 34102 43201 45777 26481 38857 56435 77962 80846 69502 78790 93874 68945 37786 69549 84586 87644 83932 69863 42629 35128 43156 39369 33683 45842 42956 59429 83831 84612 75823 94791 94720 101873 124218 141081 145348 145258 129421 115915 107637 92972 95249 84612 88118 99581 90058 97613 87047 85916 81367 83057 89275 69300 86557 97340 88329 81965 91101 84448 78323 90727 96966 98140 96460 86980 94090 105733 106929 112256 112957 95677 100368 84034 74610 63795 61436 54963 52251 65834 57817 47479 43946 45120 48376 36875 38864 42582 40408 38750 37935 35163 40408 47849 47724 53692 43718 32163 35821 39006 33587 40539 59259 41849 38664 35419 37707 50954 44154 26331 33348 37180 31965 42096 43885 56719 31324 29954 46489 43891 35857 33384 34216 44902 68280 58306 41373 64478 79637 51773 55388 74652 72723 51521 40074 52521 68478 76308 82775 61048 43287 41515 39928 40586 36999 42956 48560 58392 75848 82276 82373 81618 87917 91031 90874 124951 131186 147449 142841 107414 80731 84112 90542 96179 99723 95271 85944 91368 75589 91308 75111 71556 66300 79703 75219 67306 94641 99613 79144 84709 83291 86096 99151 96667 94901 95673 91563 94079 96167 99662 104918 108413 82720 66795 62621 55436 54251 52262 54436 51262 51376 46120 48191 55045 47561 53333 43821 38408 34163 33978 27918 35049 54105 52643 35462 39533 41778 28391 28690 32935 38425 43801 59885 58569 56928 49715 37952 56418 60908 43225 42638 59472 40700 50130 43401 46945 47603 23410 25769 37988 53278 40401 42788 57953 62910 70710 63833 71001 71904 66478 70766 70605 62549 38373 29595 30769 50407 69272 88343 65153 61637 38330 37085 43597 38640 45298 52674 56805 68207 79435 82803 84347 88048 81504 82059 93506 92777 93543 125818 102239 89107 93124 89167 85569 101837 75905 97564 115141 97308 77236 67773 67681 75638 72089 64072 81172 88564 100678 82666 79660 91835 97510 92662 95189 89759 84389 91705 100271 84410 76958 73083 79911 64399 61111 67954 59339 53621 54795 53920 60774 48251 46550 47490 52974 49735 57507 41881 39283 39582 38696 36636 41305 38533 41544 38359 38729 55356 54313 46937 30342 41926 42285 54444 59375 65392 61321 65919 48358 56919 70013 65480 56902 35498 39683 33324 20866 35971 34569 20866 30139 42717 41945 45261 53409 45788 49691 64095 65280 68078 77366 58321 43945 55173 41558 32242 31823 44091 78446 97866 54837 53033 53218 53489 49141 38971 48141 50586 44874 63392 70609 65975 64605 73220 71117 74530 78618 79607 66861 74846 86934 77177 72622 68665 70850 79683 78117 85666 109478 95662 66850 69399 69975 68790 67850 75530 78503 83699 88400 74948 71774 107586 95781 96667 85623 81726 79584 73502 91722 86255 85478 87685 85848 73977 73205 72917 72031 71145 69074 61644 67373 58687 65405 51855 64573 55730 48936 52409 55078 59508 47360 50485 52268 47610 42838 49632 60221 56347 58076 63033 60227 59543 63104 62882 50478 49820 46461 57392 60751 61295 49190 55338 48418 28236 41623 35797 27709 24823 30726 19279 34797 34341 41945 41119 40418 36042 33384 38874 41891 67420 63853 59343 43771 18980 19980 26524 23937 49205 67211 91584 72859 54805 55762 49853 45081 49984 60696 49141 62844 69807 69919 69210 71058 58741 67264 62296 53713 77606 84602 73737 78421 84079 97565 95423 81459 81932 73713 69463 75513 85862 78655 81264 72464 68470 69378 69193 68079 69666 80058 71617 84727 111440 83112 90379 93119 87004 75074 71362 64134 71276 68618 68444 68558 65661 60818 59345 58758 60302 59405 62579 63106 54263 49235 54491 59704 72652 64265 69026 65179 46149 58758 63003 64123 72467 71467 65934 55749 45390 59506 62224 67007 71166 66252 65469 47532 26225 36558 54523 51136 53680 54837 47706 34487 27404 37851 37857 38156 27068 27840 38401 37515 29324 34743 27541 24769 37700 28427 28427 46087 56762 42945 54403 47315 20920 12376 34367 42629 46820 64794 81132 83904 64588 44429 62098 57978 49728 75670 75186 70904 72123 83312 104048 108874 84159 99362 90611 75957 98491 116825 96938 104910 114318 116748 114666 110997 113780 110638 106268 114731 115688 106051 101991 94262 88806 89796 84024 83964 82067 96156 85932 99569 131816 104694 115467 108848 87673 65879 72554 68455 58296 56877 74075 74659 72070 53866 67395 67717 71130 65014 55687 56687 50926 56188 69612 67418 65620 72164 69822 60278 45775 72549 61635 61852 64196 68669 70680 43846 48977 56435 50005 50999 59110 51125 36188 51005 69411 66248 62263 47489 45390 49592 46891 21094 25219 21920 31840 37085 35672 30954 38455 36384 22236 27954 22937 22464 24111 38113 35227 43386 41483 39384 41472 43603 29894 10615 18621 37085 57065 59826 69723 69697 56349 46945 53999 55326 59472 55048 55033 55104 63035 92170 104545 106175 112431 115399 118285 117459 123313 120737 128228 122673 114161 115107 109563 108737 118994 106976 119336 135305 121293 102862 112852 114809 113151 116222 122087 121511 119881 129789 128707 133398 141801 127946 128768 123627 116459 87007 84708 106302 95790 92736 82312 74763 80991 81051 79752 66810 71816 70799 59341 62945 64147 70349 79027 58646 61093 78203 53119 61093 74001 83878 65996 60293 57609 58022 59837 46803 41960 51717 41156 36900 34715 30171 24268 49304 50050 27324 39341 56147 40074 35487 39444 43330 26877 20262 20632 32253 24165 20507 20279 24236 25595 28068 32438 32210 24410 40184 45582 48995 50380 40167 45945 50375 36672 23165 39199 37601 40515 58022 50663 49962 53332 50190 31868 55967 64244 47966 51624 50478 64861 97093 107605 107551 113334 109747 114704 127608 130206 133125 145731 128756 122749 126766 122923 126951 130425 113162 126892 127790 115577 109577 124812 137563 138047 133688 125133 128204 139183 149841 157624 157239 160880 167293 157684 149368 157983 94938 88742 155585 129965 107601 88095 100405 107921 124035 134431 76881 56674 59201 52472 43601 48635 56794 48988 43216 50076 65491 49706 57076 67121 75665 83254 64110 40074 63392 53190 56261 61218 64474 45814 35672 37498 28627 37416 51207 31672 32427 34840 45059 41145 21681 27812 42373 28165 23621 27421 26535 22279 18034 12789 13490 22279 27182 42281 41868 38324 39537 52572 56653 48369 50483 41993 33726 39672 27823 36498 42558 34552 48831 45233 54734 61865 44287 40395 66924 59945 29857 49390 55190 57480 94285 117887 119517 134952 133973 125881 124740 120816 148048 148450 140198 118424 117585 125707 125355 130562 146530 147780 146275 148905 147133 139720 135165 130567 132165 130638 130464 134834 139193 135937 122520 146976 150649 138193 117571 120842 61060 77204 127609 118665 121102 103272 91594 136459 136833 130964 54141 55326 62289 62577 38900 31584 47102 40971 29410 39857 51016 39373 46575 57583 44287 69790 52566 42330 58033 56386 63246 72263 68061 55201 39025 29584 31584 46831 48805 38042 31182 33954 39971 46102 27236 29997 33356 20849 23404 24948 21806 22051 17148 17735 22518 22464 21165 32182 41156 33264 35623 49554 52478 43988 36307 58064 34584 26997 32008 29296 46287 43700 37917 43216 57620 57104 45418 53661 56999 53536 37487 41309 55186 69807 82612 94753 96818 93926 111769 107150 99638 85382 67258 86630 118923 90721 97629 116569 115384 121625 133993 128793 131391 138621 142436 137761 134382 134984 135679 154901 150516 144946 145815 154869 146647 145163 151929 137006 111468 111354 104369 77679 72087 89105 110347 125128 85785 74302 61633 80375 75216 55055 58827 44586 40569 39634 46879 53956 40743 44754 60794 57381 61338 60013 54859 60805 62708 48831 54500 57674 54087 63517 60218 63403 50825 36498 47891 49919 40287 48358 39743 44216 39786 43330 39498 40199 29698 21561 18344 30563 28595 39569 29666 22991 23034 19333 26008 27296 28068 31894 26464 26926 38672 59190 33068 20279 26268 29296 39270 39498 33384 43575 48777 54794 50446 47016 52261 60603 60739 60010 51825 45728 63562 69177 70519 88879 89135 90656 102250 103958 115081 116210 88717 81637 92437 111328 94209 99351 102528 100089 109362 101618 101900 96080 78355 92867 101652 95200 102570 113399 102414 91235 98360 120760 98112 100465 124457 125130 133378 127959 116359 93648 91041 105026 99895 99254 76565 44468 48898 91105 86604 42782 69595 38634 37720 41802 54656 61303 52255 64175 65110 57854 47592 61067 72323 62631 62349 61446 48483 53358 56429 58614 54842 57614 65990 56902 47287 49760 54059 59304 48988 42085 32769 36840 40384 31367 28709 24404 32367 41341 51902 55805 48614 31851 29008 37210 40227 30655 29769 34797 23703 20806 31139 50472 43569 21034 23350 40156 38384 53375 51663 48831 47532 48663 41298 50685 49446 51745 57511 58169 43668 42016 51033 60491 78291 85358 83691 99100 101230 92611 105863 111474 89037 73508 80897 88443 87051 86225 85262 94121 72250 79087 74689 56323 50942 72288 64923 74783 85241 93628 88116 92873 82654 78501 91514 101869 80469 89263 110427 106784 107494 111778 108424 100499 82170 92411 91426 86207 71140 83638 83724 48869 61381 67082 67028 76420 82306 79301 63741 55919 59278 48652 46663 61839 55979 56685 64691 64104 56674 51657 50070 50184 50184 53543 57087 56788 43629 50874 45743 50216 46743 28638 26165 26937 34840 40928 41771 33720 34541 42042 42042 45586 44472 37683 45657 42113 41401 31840 48255 50021 37976 31720 32612 32840 30481 20920 26051 40569 47059 58022 51549 49244 38444 42102 40298 49973 53033 60936 54762 41842 37515 34341 46375 71405 93270 81210 71988 85745 76907 72559 72783 87536 92065 70962 76277 59427 58780 63808 70967 82333 83686 86828 92215 68026 51463 70912 40125 54067 66542 63890 58193 70690 83583 66955 96009 98026 75299 83435 84381 93435 104816 98509 78680 92514 96226 106712 100713 95044 100439 106317 108070 108594 100620 101349 101990 95923 92228 78178 49511 47831 53033 39330 49435 52104 55577 63192 53674 54902 52717 45053 44124 49113 46042 51771 56500 48059 35840 34182 33410 19621 30296 27638 17963 21980 32313 34857 42059 34965 31008 34726 34954 42330 49489 46255 41771 37156 30840 36085 58457 53141 51956 42227 37629 32367 19931 20148 28894 41341 50190 51005 46532 45102 33840 34797 35868 34857 38102 54158 48859 40352 38754 35281 39885 59360 76949 72971 65889 79760 69395 53398 57443 77697 89813 79010 60595 45294 43533 54051 56606 59449 65950 74234 72185 80746 70467 50605 52272 74969 65215 62036 51920 61471 79441 83643 72783 83366 76792 68975 67379 83304 97502 102556 87913 102553 96471 93252 99212 102536 89286 92802 97751 96205 100343 97175 102745 80194 52305 62507 60066 47788 39754 33139 50315 51517 49691 52332 47771 48369 50543 40683 43341 43455 36552 44754 52429 47401 40313 21909 21322 17550 14550 16148 14376 25937 32313 30541 32199 24279 35552 42569 42341 41743 44586 46244 42102 41814 48315 40928 38900 34128 39444 39971 35840 26236 14675 17735 40330 46586 47059 45760 46760 44863 36085 32726 37569 39814 34444 49141 44380 36808 42711 35569 51315 52044 55534 56132 54958 75803 69976 43635 52996 80262 76802 84047 58709 30232 42337 44109 44957 54247 54307 56905 60047 82393 97301 129744 139456 145712 92336 45838 59976 87600 84708 60172 47338 79435 116169 98121 95368 100265 84702 78657 92958 96069 83056 86506 98349 86084 82985 74658 83213 89515 93597 90042 99375 86435 34069 41830 47380 36042 21806 22165 52098 64698 63872 49244 45771 44711 40341 40569 35797 37025 48156 47341 41341 49956 47700 29524 14903 17262 15262 12305 10490 21578 28296 25823 27769 33068 40498 38139 35840 34840 31709 31122 36324 39683 44401 45287 39085 39786 37313 45814 36139 20621 15789 26823 46646 47874 52233 42216 37313 39743 30068 27410 31253 38330 43945 49560 34520 37580 42543 48070 46201 49560 31199 38586 52713 67003 69840 56951 71867 77789 84880 87031 53002 39260 34591 37602 56637 64178 49507 52752 80539 78055 78528 131807 171181 161669 125679 80353 86752 88709 91894 87937 73140 85059 116080 102516 93009 95841 110718 88394 83807 84426 90041 91725 77211 63118 78501 85817 72929 80852 88689 81074 81416 80783 67525 59364 41944 46684 40559 23774 53653 98154 75199 44543 39281 34851 31552 28307 32840 32296 34068 43156 42640 40939 32253 16148 8658 7359 10718 11604 13675 22279 22567 27595 36857 29051 36954 31823 30823 32296 26279 23806 27350 35253 32954 40857 42270 44857 36481 33481 30595 26165 23404 16490 38971 40259 42444 44102 34014 32900 33128 24823 24823 21464 33449 53380 53391 42021 43483 48500 47326 31666 27481 40483 53001 66693 79233 87101 84961 82875 105861 84691 65566 27112 18198 32553 37233 48643 52763 71483 70369 66053 70668 75055 123377 152484 109810 84507 71195 69238 68836 77397 90567 97691 106573 91773 80706 71299 95460 89198 71065 79820 73054 74151 75308 72630 71701 80159 79370 66491 78263 94538 87749 52366 67824 71001 54695 76362 83751 76701 89627 83588 58713 49842 39167 29780 30552 27008 28709 23051 37025 47515 33840 32840 29182 24763 12017 5473 9718 12903 17735 26812 20866 27079 38227 23148 23148 28165 25806 27692 24806 21561 23034 27165 27165 29051 31823 29165 28279 33595 33296 31410 24937 16789 24920 24752 31812 22795 24453 29296 27595 24823 32253 32671 40363 46645 49217 60012 39814 53805 47223 27606 33520 43326 53876 58192 73080 90352 84337 88408 127926 95499 91942 85895 104595 107051 111236 92627 71987 60509 53051 56410 53350 55965 95501 171626 114278 63939 64378 58894 53752 56236 72206 91931 95762 101625 80906 60346 82897 83429 72276 78370 68793 61856 63138 60873 75761 59286 62112 70263 80377 82368 96239 77482 60204 75596 74237 83994 93540 95948 87767 89311 57453 36053 35281 28307 29965 29193 25350 25051 34253 41455 34612 37085 36558 27997 9658 9245 8131 8131 15849 21094 21279 32851 42184 29464 25806 20148 18675 18789 20675 27877 30464 28165 28165 26393 29165 28823 27165 32709 34296 30823 25165 27051 30937 20849 20322 21094 20920 21763 29595 19980 31834 36748 35879 35634 33139 55093 43717 49261 54517 42526 34509 36341 40102 53631 60790 81917 81820 87278 114778 76978 113011 158830 149574 140475 124176 77881 64295 59398 58512 50142 55877 60737 94581 145619 87357 60019 53632 51436 65221 70559 78544 84159 91620 90042 72334 50703 66781 104081 105597 57933 54073 53267 55392 42723 52301 47854 47603 70474 76186 66061 77596 86299 60079 70981 68377 77650 75297 74058 67090 65655 60470 38597 43184 39466 27720 27122 28307 20877 21578 25649 33954 36612 39683 25464 5359 9131 9131 8245 10903 17735 20453 35612 48586 28475 30731 20561 21561 25920 22034 18675 23034 18490 19376 21447 21262 24507 34595 33182 24692 19262 28350 28709 29812 29638 22034 20251 20034 19920 32715 25410 28894 31563 40401 48554 35911 40988 46489 48962 47560 38683 29666 36868 50016 54631 64143 62132 66682 60622 64906 79694 101878 118898 115881 91915 83149 73668 67984 49076 47484 38755 40114 50219 109341 140303 81166 68198 56284 68662 85219 88013 88355 89073 93794 85607 61421 55991 60317 78444 89276 56947 40136 47347 35063 31547 51246 32330 41412 58728 64913 67833 59246 60910 47365 68779 78257 69106 58600 62654 72232 44152 38238 37836 40124 32210 41341 38199 38911 29008 27595 27823 26937 30296 27894 16447 6245 14675 15262 11191 17436 18436 21980 25051 28584 30019 24931 32236 28692 23262 19789 16903 17490 23333 30105 28692 19675 21148 29937 29051 22148 19675 28051 27165 22436 23507 27752 25567 24279 22692 23823 20692 27008 34264 46700 39384 31883 29225 38857 43586 29965 33797 35509 37971 45646 56805 49674 47016 65263 49631 55969 73444 126678 154905 127352 98663 82873 98784 85582 74055 63300 53517 53833 71781 105084 114338 98917 70779 50088 68320 71456 74080 80478 85908 87048 79895 38978 53991 69747 57269 62676 48457 34848 45657 36558 50936 88290 81985 76444 77023 66984 70741 85242 78736 57626 71041 77041 75445 66634 66546 54920 41075 31449 40124 37238 34210 38395 33182 29595 24165 31666 25421 17735 28709 21279 21393 30367 37982 34438 34954 27980 18376 22393 33182 24350 41036 31649 30051 32937 27692 21262 22148 25333 32404 34122 28165 19490 19262 22920 25393 27165 20920 23507 23920 23980 27980 23920 26752 25165 25937 36085 24165 31367 40384 36079 31834 26524 22279 33840 42928 45896 49978 32520 40885 40287 44700 48358 61001 68872 63171 79156 72188 114770 144530 108303 94292 82714 110556 108855 122094 135415 125147 112247 100131 75016 75543 85109 67634 56133 63107 64525 64263 72824 83336 82781 86499 51174 50245 85140 66731 120591 121759 100378 110720 113070 93638 78528 80294 94561 89054 74514 63856 82097 71030 58002 74329 59464 75326 75907 66318 54903 38705 38825 45070 31139 28193 25948 23350 23464 19621 18806 20279 13262 19034 17148 30367 53375 35797 28823 38726 34726 23176 19561 16262 15735 47879 41498 40139 30350 21148 23034 28877 38774 32589 20860 25920 18789 17604 21561 24806 24692 25692 27578 24208 18963 26692 23806 19148 21692 33655 36427 30182 32481 30595 35666 26649 29997 29367 33911 47913 55528 49896 34971 45130 46358 39156 43173 58702 73003 83173 79401 62829 99617 148713 139850 91386 85597 117833 153191 158595 135467 103713 82979 81190 77287 70905 72759 77195 84311 79952 74864 72123 66491 77080 67557 58333 51653 58436 57393 98835 161185 158456 158428 151494 97185 69548 64933 66275 69232 63036 61378 61290 68030 51877 53002 60187 53273 59421 63264 68096 49038 37879 36167 31851 20877 18404 20404 29079 16447 14675 16148 20393 23165 19034 20578 34982 42358 36612 23219 23219 24638 31367 26350 46167 38950 45933 42253 53814 37666 18262 20561 35290 35122 38780 23860 17903 16789 21077 18490 19675 20262 31524 27980 21436 17789 28051 26051 22692 29051 42629 33840 26051 25279 18447 35253 29410 30655 36199 38857 47326 45266 42042 45347 47304 46945 53098 46668 62300 62958 66975 73390 72917 90019 122039 91874 89013 93372 103640 129813 104657 72912 73678 68672 67601 66530 65763 72144 68014 78158 78995 75098 77488 66394 74542 66187 43673 26791 43320 43810 103308 136537 135722 153727 82986 39626 48458 48871 53056 65933 55464 55105 56675 62615 47430 53284 50518 53105 57182 56872 49784 37124 32335 34922 24649 21877 21176 26133 25948 22464 17920 10017 16034 19393 11675 12262 29954 26068 25937 25931 32475 33481 35139 47358 49098 48358 59907 51754 50868 42139 39954 34404 24447 29578 32937 27279 28279 25920 25034 30051 31937 24920 31279 29567 21376 19675 26866 35068 31008 26040 37971 31840 26051 26051 25692 32182 34715 35313 35498 33367 38498 43195 36270 38857 47358 44070 42597 55973 62947 58474 65149 72781 77929 85880 90470 60394 77695 85424 87843 78151 56007 41891 55474 60257 60371 54582 60137 57778 58453 70771 75967 71737 69580 81223 81374 53898 34221 22475 24905 33460 93508 82910 139748 158542 125193 89898 81756 65343 63383 64318 54034 52077 46348 46761 44413 37228 43077 48507 39565 37135 59481 46066 25019 28720 19219 20991 18045 25535 22404 17920 15148 10490 16148 20393 8903 21866 24812 20866 30296 31008 38683 32139 29133 47309 40270 39601 51363 43737 44851 49156 51167 45438 43911 37595 44726 41954 38595 27393 31051 34535 32236 27692 19789 25034 24034 17305 22621 29236 28752 26567 29410 35954 35128 32769 24393 24681 29997 30182 35498 34612 40857 42782 43010 35324 36982 42184 38341 57620 58876 65947 75334 74710 66269 62209 64024 63078 59887 47027 56061 58115 42042 39461 26182 51158 72003 61784 43189 39118 54311 55442 71911 82150 64823 68612 73509 51778 29492 32221 35178 42716 55174 80181 154069 156129 161656 154802 154987 139335 78400 67415 55430 47701 41303 45189 48630 33798 44316 47909 32178 31591 47952 45582 33705 25361 26133 35281 22062 13675 14974 14675 8017 12262 15920 18920 17148 22567 27997 34324 21279 18806 14262 16262 29438 32210 37726 43466 40079 41737 48341 41438 45210 47982 47096 44324 47498 45797 39367 30279 36296 35823 29507 25034 17789 18903 16017 17903 20849 22735 26165 28339 36954 37128 32655 29997 22681 24681 17262 26937 34726 34797 36498 36900 36384 37743 40988 45016 43586 40988 50734 60588 52081 57326 63756 64343 47999 47700 34737 36868 47586 37025 24225 39042 41700 46027 63502 66274 38933 46907 55115 42842 56143 53969 59399 57485 57442 66410 26720 29851 37580 37933 38705 108106 151320 163200 160314 148318 144507 133410 72768 51587 55456 54912 36275 28606 40004 52946 60399 52659 50485 42397 32107 32150 41602 27258 36754 35569 29666 32623 15447 9718 8017 13376 21507 29997 27296 20909 31840 30552 18621 25339 22279 29150 35965 33780 31464 35085 35008 46341 48227 46569 46569 43210 46096 39438 44911 43253 45911 41954 34122 42367 27507 21789 24860 18490 16017 19262 22034 25621 29165 26866 28165 31812 31584 27752 25393 27350 26578 29296 29709 30307 35726 34530 35313 42999 43173 41287 34612 39629 49005 49728 43466 40438 38694 47238 44227 39857 26350 38210 35911 20795 29584 41760 47532 49190 51788 54870 50380 59556 67633 52158 45027 50810 58855 65775 50941 59137 40993 26421 24834 23649 50608 77806 97067 159047 154905 147752 143550 135909 86594 52271 65222 49949 26714 24176 29204 44445 34993 29481 42782 45255 38167 44004 48086 32318 33623 25008 31324 53414 29378 26008 15746 14860 34780 26752 30943 26296 16920 18148 19034 23393 30954 37096 32464 26051 30182 23524 32002 35008 44982 42150 43139 42438 46797 38193 41737 42139 50156 48743 42840 40552 21387 13256 17615 24034 22148 18675 18675 22148 28165 24507 21920 25464 26866 31769 29709 20920 28464 30595 33367 31253 32840 32068 30954 39444 43173 33324 27296 39031 48005 50136 35025 33894 47412 50298 41341 36840 46700 46532 31715 17436 31758 25100 28872 41042 39754 33552 38395 38526 42657 56756 51098 56816 53457 54132 48674 34324 43472 33025 26823 22165 46597 35287 120104 154176 143894 130143 122360 110218 68755 58308 71379 60886 43787 26013 30774 37520 36993 31068 43765 46021 51038 44591 33372 26247 20404 20290 40836 53784 52300 54844 49528 47283 53055 33438 24883 28182 24649 23051 22980 18806 26524 36683 27247 25350 27410 35019 31290 34709 33720 29817 31763 41438 35595 30649 34307 41025 42498 42498 37655 34649 22387 19501 17256 24034 23034 17376 16017 19376 23735 24034 21148 23105 22393 23279 30524 20148 20322 28823 30595 29780 27421 35634 31481 33068 42586 33025 37085 40917 42874 45233 33965 39264 40150 40737 40438 32894 42042 46418 41390 23980 26214 22442 19681 21219 31193 42683 37324 31780 34666 40765 54175 56702 51027 43059 35156 22165 25008 28367 23752 23937 21524 42748 123708 120785 119269 106204 98851 102395 83920 64000 59271 61761 71954 70524 52847 45771 45999 41580 42477 41363 47380 32905 25056 20002 31748 43135 50462 51126 57317 52588 51186 53300 55300 46369 21279 15675 23828 21703 13778 17333 26122 26894 24774 24518 28692 37780 32649 33421 31763 31236 31051 31290 32720 34606 32937 32709 30894 31823 39079 34763 26333 21202 23501 25806 23148 15718 22735 26094 27094 23034 20262 19088 23116 24806 23806 23034 23094 23589 23105 26937 28122 31019 31008 28524 34954 36427 42216 36971 29068 38085 29763 25931 30116 19387 36780 39085 33840 34726 32068 26524 22382 22567 20393 27464 37552 48999 50885 26763 43754 51098 48087 41412 60246 46603 38341 24111 17507 13561 26410 30367 31786 64212 96251 74730 91997 93453 90758 82661 85678 88635 83732 70453 65556 76835 65921 46141 46455 41335 40694 39107 34802 38150 43879 30546 33677 48722 46793 46266 46326 47027 33395 45853 49283 51098 36868 25176 27469 19931 13376 20333 13088 16860 27279 20675 18148 16077 35475 32062 35720 37894 32823 38307 39677 34720 33823 33709 22920 28105 35073 34948 30888 25686 35236 30105 18615 21675 25322 28567 25795 23208 25806 18561 27937 27350 18860 21262 21746 18077 21621 24578 26464 25393 30709 33470 34068 29997 32242 34085 36672 36438 20159 14430 17028 12370 23507 29051 33780 40868 40814 39803 24812 33199 30954 27578 31535 49537 43221 22290 44597 88033 87876 65356 100046 76461 40760 36846 19094 11903 24823 38971 43618 44635 51358 75414 73072 72001 73018 70149 65306 66910 67149 77308 73351 68964 66904 60229 45281 36606 33905 33916 38275 38264 46879 36204 33845 45950 40765 42537 41494 44152 37455 30851 37167 37694 41651 38802 33714 18284 22290 14376 6772 15789 16903 14131 14376 18621 33589 37546 31062 31051 28632 31361 35791 37492 37965 39150 38193 29578 38133 41916 31942 35002 31176 32464 27806 18903 16718 20561 21262 18664 16490 17789 22806 22415 23931 19262 16903 19262 22034 27464 27176 23806 28154 29111 30296 26638 25453 33726 41526 38036 17028 13843 14544 15142 25458 29002 32432 32378 45717 38216 25638 33840 26236 22045 37600 53417 34677 37922 51315 87751 98323 62790 85196 63345 40287 25154 25225 17806 19208 27182 29584 36003 50549 75323 53717 55087 55500 71263 67349 51902 51657 57990 60121 57631 56631 49782 36694 44939 38449 31774 29774 36204 43520 27703 36258 46531 42363 34449 38939 40597 37466 37808 34324 39580 45591 40813 33600 24828 21404 14572 12843 11772 8957 8843 9903 20681 32888 33888 25632 30877 35361 34546 31763 39780 35595 36780 42922 40682 37546 33649 33475 35187 32105 24148 30806 19789 17017 16903 15245 14832 18903 17903 17202 20159 20148 21148 17376 19675 21920 26578 29464 25578 27926 27595 25165 25638 26937 32954 45472 44298 22458 11658 14430 25643 39617 31475 33193 37569 42586 40113 37373 42689 35210 26404 43600 59998 38731 37324 62605 68003 82663 51261 41689 39216 35672 29068 18507 23453 24926 22453 25040 33416 48130 44048 52717 55526 54788 64095 58164 44156 40139 50358 52435 54392 59893 45113 40275 30834 26105 36019 45776 49152 51978 25002 37959 38449 41178 38520 39124 39939 32264 31965 27780 29421 40329 45514 43916 28127 15675 12088 19561 11017 9544 14675 14262 8131 36796 27583 27447 34834 37318 36546 33948 28464 29649 28991 43334 39149 23561 31518 31045 35116 30817 22088 27034 20490 16903 17903 17490 16789 21849 23507 21561 20675 20262 22034 24393 18262 19262 24279 22393 25290 24866 27236 22692 25866 25578 37270 50033 53278 37569 31481 29062 34959 32948 30877 27823 29410 32666 38330 38803 40874 33253 21333 25925 56209 57645 44107 57061 58061 68074 52588 23268 33356 26812 18208 23165 14077 11604 13077 13963 34313 31655 29242 45233 50874 56865 61725 61882 46999 40666 45868 45646 47304 52332 54033 47580 39079 21632 28589 45950 50853 44896 41993 39372 42036 39036 34150 33210 33324 24176 29606 38737 34492 35959 41557 37013 28725 13686 9131 12903 17148 14963 20991 22991 19931 62547 24284 25866 45172 38796 40725 25931 40731 35372 33540 41138 27344 25746 34176 27632 27632 33415 32703 23447 19789 20376 19789 22561 17789 22322 20148 22447 21034 24034 25507 33840 30008 25279 27051 21034 22518 25578 28709 26350 22920 34068 43173 48375 50207 41999 44771 45412 52070 30062 20860 30595 34253 30481 30057 33726 35384 32253 17974 31948 38432 45395 42580 41700 38515 56941 57833 21382 15490 19208 28040 28698 28638 18436 22980 30997 22752 12664 47674 70123 52506 51979 59594 55822 55386 49227 43569 43956 41700 44315 51642 39036 35677 35976 37862 45950 46537 46070 40107 31703 31307 35720 35133 30008 30965 27236 23763 38378 34193 31643 45557 45987 24643 18170 10142 16654 11316 13376 27823 26535 34780 40622 47355 52574 48710 53405 65607 29404 49041 45796 29572 46209 56095 29404 28475 27159 26632 35079 39851 32535 28703 28051 25219 16615 17017 20262 16490 18789 22148 19789 23507 27752 32008 30122 28823 23806 19561 19860 20148 26578 25279 30182 39515 45777 46375 48848 52577 59964 60050 45341 27763 28638 30182 29595 28812 27823 33601 30481 19273 34780 42928 41814 67448 60605 45532 50087 49560 21268 15664 12077 23681 24094 17322 24567 24165 32943 35530 24339 56246 73379 55822 42244 49218 54936 53517 53147 44287 30008 37509 43070 39868 34421 29660 33688 45896 45537 41808 42580 47765 46754 38079 37133 27649 27307 27720 17447 19333 24404 29361 28757 42127 38540 15985 19871 14202 6658 10544 10430 20333 19148 27133 74085 83085 51955 50362 58362 48992 42568 49340 29942 16148 40405 49035 21860 30230 28703 31763 33019 38449 39335 36851 30051 23034 18675 17903 23920 27937 22920 19675 17718 21034 21148 21148 23920 27051 24578 19045 23703 20447 23219 21621 25453 36857 34313 42586 47603 53936 56850 61850 61964 48261 26350 26051 25464 26051 32068 33242 22692 14914 24045 37552 48070 65149 52033 49147 58121 46375 16436 11718 9544 12131 10903 11305 14490 15675 14262 27399 41461 41945 42244 43478 33281 40668 50207 50272 45255 41515 28350 33367 40939 37395 30247 24301 29606 37737 34378 43993 50896 53565 58266 49825 33894 24535 27780 25660 14501 15376 24404 35785 37959 44600 31583 16153 18572 15447 13903 20746 7729 26176 38378 36720 95227 77977 65340 90672 73803 80917 75906 65536 38561 56942 52014 41768 45458 52187 48415 44834 36503 34677 36851 36666 34378 27475 35492 32008 19447 32954 27051 17017 23034 23507 24393 23806 22447 26866 27937 28791 26834 23920 21034 21806 23692 39988 37444 45788 46614 45674 52523 53050 50104 45304 29769 27638 27997 20806 24279 30883 27877 22985 35791 47053 48532 47005 42102 42874 46891 41287 21980 13604 12131 7946 11419 6473 6886 11903 13963 20866 26296 30427 49147 44478 35629 34868 40945 45429 42825 36438 36025 44754 38982 28606 33432 28187 22991 26948 34851 41580 44167 51765 52309 53440 42395 29290 33666 20806 15088 16387 27404 36187 41899 45312 34355 17871 26888 15860 8028 14789 14675 22931 37324 49999 96244 102401 85689 75136 76244 83315 81934 77923 55557 95672 73487 57910 53572 64383 68867 36518 32019 27051 30350 30535 34976 32546 30948 29834 15131 31894 26763 18430 21974 17604 22920 22806 19675 17490 22621 23991 24866 28051 23034 21920 24393 36857 35270 39401 45315 40885 46016 45130 34498 39444 27225 25752 30182 25165 23806 26937 33595 39247 42808 46412 37982 43928 35313 36971 40216 25567 21507 13191 10245 10718 14191 9658 9245 9245 15077 23681 16436 39928 37999 27128 38173 33395 40031 44287 38808 36324 38270 43700 42939 39036 41808 29290 19746 27649 32062 33834 37036 45922 46580 47352 49782 39640 48386 28193 18034 25763 22398 24458 35355 40355 28871 27247 23002 17860 10256 8071 7843 17800 19333 34666
220301 132979
Ограничения
- Время · Python
- 3000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 12 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Это задача на аккуратность: оба просеивания разобраны в статье, и счётчик надо увеличивать ровно там, где сравниваются два элемента массива. Проверьте себя на первом примере: в массиве из шести элементов у ячейки 2 только один ребёнок.
2Подсказка 2
Самое коварное место — спуск снизу вверх, когда у узла остался один ребёнок. Сравнивать там не с кем, но спуститься нужно: иначе тонущий элемент никогда не попадёт в этот лист, и куча сломается.
3Идея
Обычное просеивание платит два сравнения за этаж: дети между собой и больший ребёнок с тонущим. Просеивание снизу вверх отделяет эти два вопроса. Сначала оно находит путь, по которому пошёл бы любой тонущий элемент, — путь больших детей, по одному сравнению на этаж. Потом ищет на этом пути место для элемента, поднимаясь от листа. Если элемент маленький, а во второй фазе сортировки так почти всегда и бывает, место у самого дна, и подъём стоит одно-два сравнения.
4Разбор
Обе функции просеивания — как в листинге pixels статьи. Шаг 3 удобно делать подъёмом от j к r: держим x «в руке», меняем его с a[j], переходим к родителю, и так до r, куда кладём то, что осталось в руке. Обмены получаются ровно те же, что сделало бы обычное просеивание, — проверьте, что оба варианта дают один и тот же отсортированный массив.
На фотографии из второго примера получается 220 301 и 132 979 сравнений: снизу вверх экономит 40 %. Но посмотрите на закрытые тесты с одинаковыми числами. Если все числа равны, обычное просеивание останавливается на первом же этаже — тонущий элемент не меньше детей. А снизу вверх всё равно спускается до самого листа и поднимается обратно до корня: на двадцати тысячах равных чисел оно проигрывает в разы. Об этом предупреждает и Джордж Спелвин в сообщении к изменению ядра Linux: при множестве одинаковых ключей новый вариант хуже старого.
4+Решение
5Сложность
Обе сортировки — O(n log n) сравнений и O(1) памяти сверх массива. Для n = 20 000 это меньше миллиона сравнений.
6Типичные ошибки
- Забыть последний лист без брата. Спуск заканчивается в узле с одним ребёнком, и элемент туда уже не попадёт. Результат — неверная сортировка и другое число сравнений: так ошибается первый пример.
- Остановка подъёма по «меньше или равно». Условие — строго
x < a[j]: на равных подъём продолжается. С другим условием обмены и сравнения на повторяющихся числах разойдутся с образцом. - Выбирать правого ребёнка при равенстве. Правый выбирается, только если левый строго меньше; иначе пути спуска в двух вариантах разойдутся, и сравнения на повторяющихся числах тоже.