# The rise of the weird… Things Insertion Sort

QUESTION

Bangalore City, where peace prevails most of the time. Not everyone is a huge fan of peace, though. Certainly not Mr. XYZ, whose identity is not known to us yet. Mr. XYZ has somehow managed to bring vampires and zombies to Bangalore City to attack and destroy the city.\n\nFatal Eagle, an ordinary citizen of the city is extremely worried on seeing his city being attacked by these weird creatures. But, as of now, he has no power to stop these creatures from their silent attacks. He wants to analyze these creatures firstly. He figured out some things about these creatures, like:\n\nZombies have power in terms of an EVEN number.\nVampires have power in terms of an ODD number.\nIf he sees a zombie or a vampire, he marks them in his list with their power. After generating the entire list of power of these creatures, he decides to arrange this data in the following manner:\n\nAll the zombies arranged in sorted manner of their power, followed by the total power of zombies.\nAll the vampires arranged in sorted manner of their power, followed by the total power of vampires.\nYou’ve to help him produce the following list to help him save his city.\n\nInput constraints:\nThe first line of input will contain an integer N, denoting the number of creatures. The next line will contain N integers denoting the elements of the list containing the power of zombies and vampires.\n\nOutput constraints:\nPrint the required list in a single line.\n\nConstraints:\n1<=N<=103\n.

“TESTCASE_1”: “6\n2 3 10 12 15 22\n###—###SEPERATOR—###—\n2 10 12 22 46 3 15 18”, “TESTCASE_2”: “10\n733 828 408 177 910 108 583 290 131 394\n###—###SEPERATOR—###—\n108 290 394 408 828 910 2938 131 177 583 733 1624”, “TESTCASE_3”: “1000\n828 23 788 497 707 149 705 832 644 92 32 838 377 240 75 840 235 233 412 602 666 515 576 448 678 729 603 476 777 974 660 6 167 484 203 558 656 231 621 1 132 785 504 371 982 766 783 291 483 821 216 403 54 180 293 938 237 188 936 30 51 378 836 510 620 470 772 607 223 191 567 323 316 743 68 395 727 245 269 125 441 440 961 300 904 949 73 794 686 443 130 713 616 556 498 616 642 938 750 48 189 219 53 287 695 479 807 836 775 607 403 138 988 434 867 77 227 176 752 678 687 307 245 712 222 726 33 878 822 506 524 795 534 923 606 433 585 592 788 60 592 490 234 549 141 758 980 582 801 954 433 955 903 46 955 79 851 805 302 431 548 2 458 408 718 655 23 703 474 950 214 394 962 270 170 566 504 129 542 829 433 411 420 382 162 365 599 530 630 678 705 466 154 533 63 780 410 648 311 109 763 173 18 832 370 597 796 210 87 914 576 357 569 267 917 265 389 902 219 493 482 287 523 705 196 6 402 587 696 221 595 99 598 61 731 692 959 751 1 10 89 345 801 408 613 825 39 979 483 626 453 345 683 814 579 291 235 519 47 957 82 44 960 196 928 878 966 102 353 169 752 537 70 54 109 536 139 308 487 671 85 698 400 832 991 28 905 151 363 895 467 191 871 392 492 206 710 420 809 804 578 544 662 894 610 570 708 554 153 563 915 27 5 756 296 738 358 953 585 797 364 525 595 769 939 428 165 518 886 42 482 742 39 712 951 57 268 487 827 860 584 366 97 908 345 611 625 534 261 223 572 559 405 105 897 421 361 90 557 855 872 502 851 212 956 331 722 476 387 19 997 992 533 839 343 687 235 876 952 443 831 672 429 231 344 513 788 773 57 268 725 349 766 737 298 548 971 662 652 813 784 401 332 397 608 992 708 986 873 237 132 572 697 624 770 408 671 217 131 735 496 924 421 715 329 190 147 943 568 826 775 737 792 303 749 309 679 351 48 846 933 855 381 123 410 231 604 260 65 857 300 241 78 655 503 514 694 397 814 842 207 236 314 36 870 733 78 405 251 945 554 622 771 986 380 800 631 369 204 817 867 719 737 695 50 740 956 290 331 690 931 370 292 780 907 657 95 743 462 359 44 797 54 808 95 526 703 710 926 699 508 12 172 156 66 491 628 175 451 971 883 835 490 351 567 547 150 251 408 147 601 518 70 653 808 618 425 708 467 988 943 469 63 742 415 356 64 645 977 149 481 584 480 868 904 70 620 371 22 463 104 424 455 859 954 748 736 629 473 780 165 123 511 128 225 256 150 404 379 652 430 123 172 106 873 460 846 696 353 215 883 706 704 666 337 362 877 92 851 666 429 718 542 887 747 392 122 949 291 762 852 947 973 3 881 469 183 195 791 664 500 681 299 764 460 992 38 250 388 815 716 615 224 621 521 595 290 947 22 383 966 942 381 857 822 800 402 178 850 448 980 821 445 574 670 200 342 392 512 14 127 210 675 297 698 541 135 265 626 396 820 880 235 261 199 736 394 976 485 989 213 260 330 50 562 206 711 481 791 850 288 380 734 359 614 302 781 773 313 128 516 79 238 91 838 777 596 529 393 66 884 581 287 7 289 57 86 531 933 129 13 16 291 142 646 67 962 178 67 881 8 640 323 28 161 247 431 775 289 57 412 273 415 458 361 307 347 654 443 179 805 280 402 653 556 460 277 885 696 298 999 385 130 315 949 850 374 218 337 508 303 34 757 321 497 456 219 916 131 48 564 601 490 589 101 676 342 521 342 728 368 356 972 511 985 472 199 98 394 410 310 427 870 663 442 787 937 216 36 358 740 362 975 569 666 389 481 225 888 708 143 132 321 385 516 304 714 530 856 897 676 893 184 890 896 900 654 833 597 61 822 603 280 520 144 543 94 475 129 38 576 592 302 858 436 485 627 711 175 630 111 39 730 137 461 397 384 259 976 229 695 21 82 961 579 901 374 400 770 613 751 875 985 818 64 718 325 568 998 51 721 607 803 347 85 587 311 888 50 98 634 343 543 876 285 265 893 866 510 837 780 409 342 818 273 531 185 272 877 954 481 710 648 802 666 125 30 337 898 225 698 759 987 217 659 612 532 200 232 627 665 495 225 806 110 976 695 282 350 478 71 628 378 37 661 665 260 643 2 246 673 227 176 200 363 307 833 29 45 347 947 981 736 98 27 768 612 409 989 322 898 55 482 841 815 653 48 719 169 92 368 498 200 648 899 95 508 335 793 525\n###—###SEPERATOR—###—\n2 2 6 6 8 10 12 14 16 18 22 22 28 28 30 30 32 34 36 36 38 38 42 44 44 46 48 48 48 48 50 50 50 54 54 54 60 64 64 66 66 68 70 70 70 78 78 82 82 86 90 92 92 92 94 98 98 98 102 104 106 110 122 128 128 130 130 132 132 132 138 142 144 150 150 154 156 162 170 172 172 176 176 178 178 180 184 188 190 196 196 200 200 200 200 204 206 206 210 210 212 214 216 216 218 222 224 232 234 236 238 240 246 250 256 260 260 260 268 268 270 272 280 280 282 288 290 290 292 296 298 298 300 300 302 302 302 304 308 310 314 316 322 330 332 342 342 342 342 344 350 356 356 358 358 362 362 364 366 368 368 370 370 374 374 378 378 380 380 382 384 388 392 392 392 394 394 394 396 400 400 402 402 402 404 408 408 408 408 410 410 410 412 412 420 420 424 428 430 434 436 440 442 448 448 456 458 458 460 460 460 462 466 470 472 474 476 476 478 480 482 482 482 484 490 490 490 492 496 498 498 500 502 504 504 506 508 508 508 510 510 512 514 516 516 518 518 520 524 526 530 530 532 534 534 536 542 542 544 548 548 554 554 556 556 558 562 564 566 568 568 570 572 572 574 576 576 576 578 582 584 584 592 592 592 596 598 602 604 606 608 610 612 612 614 616 616 618 620 620 622 624 626 626 628 628 630 630 634 640 642 644 646 648 648 648 652 652 654 654 656 660 662 662 664 666 666 666 666 666 670 672 676 676 678 678 678 686 690 692 694 696 696 696 698 698 698 704 706 708 708 708 708 710 710 710 712 712 714 716 718 718 718 722 726 728 730 734 736 736 736 738 740 740 742 742 748 750 752 752 756 758 762 764 766 766 768 770 770 772 780 780 780 780 784 788 788 788 792 794 796 800 800 802 804 806 808 808 814 814 818 818 820 822 822 822 826 828 832 832 832 836 836 838 838 840 842 846 846 850 850 850 852 856 858 860 866 868 870 870 872 876 876 878 878 880 884 886 888 888 890 894 896 898 898 900 902 904 904 908 914 916 924 926 928 936 938 938 942 950 952 954 954 954 956 956 960 962 962 966 966 972 974 976 976 976 980 980 982 986 986 988 988 992 992 992 998 253576 1 1 3 5 7 13 19 21 23 23 27 27 29 33 37 39 39 39 45 47 51 51 53 55 57 57 57 57 61 61 63 63 65 67 67 71 73 75 77 79 79 85 85 87 89 91 95 95 95 97 99 101 105 109 109 111 123 123 123 125 125 127 129 129 129 131 131 135 137 139 141 143 147 147 149 149 151 153 161 165 165 167 169 169 173 175 175 179 183 185 189 191 191 195 199 199 203 207 213 215 217 217 219 219 219 221 223 223 225 225 225 225 227 227 229 231 231 231 233 235 235 235 235 237 237 241 245 245 247 251 251 259 261 261 265 265 265 267 269 273 273 277 285 287 287 287 289 289 291 291 291 291 293 297 299 303 303 307 307 307 309 311 311 313 315 321 321 323 323 325 329 331 331 335 337 337 337 343 343 345 345 345 347 347 347 349 351 351 353 353 357 359 359 361 361 363 363 365 369 371 371 377 379 381 381 383 385 385 387 389 389 393 395 397 397 397 401 403 403 405 405 409 409 411 415 415 421 421 425 427 429 429 431 431 433 433 433 441 443 443 443 445 451 453 455 461 463 467 467 469 469 473 475 479 481 481 481 481 483 483 485 485 487 487 491 493 495 497 497 503 511 511 513 515 519 521 521 523 525 525 529 531 531 533 533 537 541 543 543 547 549 557 559 563 567 567 569 569 579 579 581 585 585 587 587 589 595 595 595 597 597 599 601 601 603 603 607 607 607 611 613 613 615 621 621 625 627 627 629 631 643 645 653 653 653 655 655 657 659 661 663 665 665 671 671 673 675 679 681 683 687 687 695 695 695 695 697 699 703 703 705 705 705 707 711 711 713 715 719 719 721 725 727 729 731 733 735 737 737 737 743 743 747 749 751 751 757 759 763 769 771 773 773 775 775 775 777 777 781 783 785 787 791 791 793 795 797 797 801 801 803 805 805 807 809 813 815 815 817 821 821 825 827 829 831 833 833 835 837 839 841 851 851 851 855 855 857 857 859 867 867 871 873 873 875 877 877 881 881 883 883 885 887 893 893 895 897 897 899 901 903 905 907 915 917 923 931 933 933 937 939 943 943 945 947 947 947 949 949 949 951 953 955 955 957 959 961 961 971 971 973 975 977 979 981 985 985 987 989 989 991 997 999 245909”, “TESTCASE_4”: “0\n###—###SEPERATOR—###—\n0”, “TESTCASE_5”: “0\n###—###SEPERATOR—###—\n0

``````#include <iostream>
#include<algorithm>
using namespace std;

int main()
{
//cout << "Hello World!" << endl;
long long int i,a[1002],sum=0,n;
cin>>n;
i=0;
while(i<n)
{
cin>>a[i];
i++;

}
sort(a,a+n);
i=0;
while(i<n)
{
if(a[i]%2==0)
{
cout<<a[i]<<" ";
sum+=a[i];
}
i++;
}
cout<<sum<<" ";
sum=0;
i=0;
while(i<n)
{
if(a[i]%2!=0)
{
cout<<a[i]<<" ";
sum+=a[i];
}
i++;
}
cout<<sum<<" ";
return 0;
}``````