P14961 [HackerEarth] Vidur is very much interested in Job scheduling techniques being used for improving the performance of computing systems. This semester he has been working on developing some new methods
普及
题目描述

Vidur is very much interested in Job scheduling techniques being used for improving the performance of computing systems. This semester he has been working on developing some new methods to schedule jobs on a computer.
Today, he is testing job scheduling using Dequeues on his system. The jobs which need to be processed by CPU are stored in a Dequeue. Each job is assigned some priority value P. Every time scheduler selects a job from either end of the Dequeue.

Now to counter the problem of Aging, he uses a method different from the existing ones. If the scheduler has to select a job, the priority value of a job becomes P * a, where a is the age of that job.

To analyse the data later, Vidur saves the sum of priorities of each job in a file.

Now, the scheduler works like this. It selects the jobs in such a way that the sum of priorities of the jobs is maximized.

Note:
Priorities are considered just when a job is processed.
The first job has age a = 1. Each job takes one unit of time to get processed. Thus, the age of second job would be a=2.

INPUT:
The first line of input contains N which represents the number of jobs to be processed.
Then N lines follow.
ith line contains the priority value of ith process.

OUTOUT:
Output the sum for each set of jobs in a single line.

Constraints:
1 < N ≤2000
1 ≤ P[i] ≤ 2000

SAMPLE INPUT
4
1
2
1
4

SAMPLE OUTPUT
24

Explanation

The order in which jobs would be processed are 1,2,1,4. Then, Sum = 1x1 + 2x2 + 1x3 + 4x4.

输入格式

见题面

输出格式

见题面

样例输入
1258 917 293 554 790 79 497 671 399 692 278 916 426 241 895 330 90 854 871 87 490 452 372 877 831 900 104 479 882 571 501 633 13 708 461 115 659 436 805 650 214 639 997 822 998 352 403 666 850 724 69 565 264 632 148 830 513 315 882 302 745 939 894 348 435 21 254 573 630 511 710 850 377 408 545 126 509 136 976 94 387 585 252 94 406 357 424 85 484 670 338 166 455 299 618 81 877 612 308 478 468 879 5 71 173 317 936 27 937 6 214 359 952 751 392 432 935 864 954 15 395 200 447 306 438 28 155 461 474 589 654 472 93 852 319 564 750 34 961 264 555 228 897 849 496 190 155 63 348 396 549 406 20 253 865 972 592 920 739 426 754 328 292 30 466 931 817 557 856 484 19 444 931 776 824 93 51 548 589 632 211 599 440 510 809 12 587 6 386 617 89 801 424 677 679 934 524 119 681 965 408 63 186 246 639 628 548 223 987 968 818 101 960 341 391 294 271 296 602 359 770 981 662 137 988 496 8 662 881 714 177 930 666 898 944 967 694 213 292 691 457 832 459 12 550 20 343 636 535 356 50 563 527 80 516 417 924 82 328 798 351 85 791 212 682 116 905 175 957 784 454 33 129 540 748 241 455 216 92 826 945 887 198 426 790 115 403 405 118 85 565 29 662 388 979 83 984 682 193 623 800 433 36 651 449 629 767 344 317 602 423 235 679 40 839 316 959 930 302 96 944 991 88 785 800 197 708 835 181 940 766 667 176 409 766 202 537 655 507 586 995 212 930 686 745 222 530 846 268 486 469 907 518 845 463 763 421 460 229 701 211 436 725 108 3 867 257 277 175 9 667 312 176 161 168 120 764 91 85 415 979 764 310 690 743 501 264 432 232 59 141 661 711 431 780 826 384 215 403 368 211 295 869 864 355 427 472 137 551 45 757 47 903 716 373 48 402 530 235 454 195 66 586 645 902 163 480 238 58 192 441 859 862 200 800 102 168 553 774 169 276 949 473 434 189 506 743 299 201 588 250 244 121 453 927 372 125 414 141 61 459 561 374 132 42 566 980 978 129 791 111 883 912 676 591 16 56 3 993 217 837 975 21 588 558 938 553 530 412 901 216 502 554 516 7 337 209 940 879 44 205 701 302 200 524 507 746 407 665 851 230 951 114 586 102 902 240 235 314 48 433 166 440 15 638 671 765 91 9 102 816 769 896 486 35 831 254 46 115 359 76 893 748 822 149 216 938 637 6 696 376 482 196 10 804 531 938 305 197 271 676 376 21 407 359 85 126 634 174 177 273 21 657 666 587 342 937 904 834 109 335 778 58 538 344 666 578 11 341 77 644 249 926 245 657 31 202 341 450 32 298 47 238 584 761 476 714 847 955 726 86 474 884 17 643 527 430 625 850 140 819 143 166 439 483 905 574 580 733 260 149 515 123 592 239 900 469 812 964 665 983 338 618 96 939 300 719 536 571 438 230 210 356 757 767 12 673 832 633 824 860 55 321 365 378 692 32 736 281 395 188 308 63 285 581 387 617 726 556 667 854 516 313 870 192 158 62 349 282 505 856 892 962 106 818 900 50 901 647 617 214 152 958 32 935 901 929 609 221 535 552 830 179 694 820 31 249 373 24 743 868 997 56 769 780 848 215 518 60 505 186 81 584 642 881 428 763 452 854 244 758 956 890 623 97 441 546 602 374 581 316 67 177 627 259 758 573 429 833 399 903 422 294 352 467 304 985 748 275 301 924 728 183 915 241 151 281 384 934 930 20 766 443 98 43 878 806 310 634 139 40 823 762 362 681 381 378 968 743 38 559 604 830 626 573 113 670 583 293 992 525 10 268 649 128 728 630 647 780 665 5 402 956 8 601 137 897 886 64 990 192 316 334 715 462 674 577 581 598 24 384 742 158 446 690 195 760 126 802 307 407 722 178 183 573 8 557 97 659 437 24 257 238 83 104 356 81 224 634 709 662 676 539 65 400 358 538 276 433 455 821 189 229 184 624 567 28 522 332 904 335 854 168 800 702 754 687 579 969 791 522 849 735 748 138 295 864 982 562 587 804 671 203 850 612 422 116 113 555 399 939 850 170 301 698 948 141 574 309 360 315 914 977 450 215 986 847 141 37 835 955 424 467 45 947 884 889 354 24 26 453 911 207 973 540 499 577 746 36 86 70 454 945 1000 668 64 17 104 634 302 597 924 833 483 269 649 604 966 454 459 268 962 169 569 686 676 428 128 432 243 935 685 489 178 766 166 269 438 726 940 27 989 681 322 489 461 990 246 95 142 796 750 967 735 141 8 355 924 794 677 680 492 118 931 331 517 655 714 533 193 763 362 602 923 461 19 28 728 156 222 777 417 492 419 695 490 217 926 78 979 677 256 990 222 183 344 909 914 254 764 718 761 539 129 30 231 205 772 364 861 570 236 442 326 439 129 736 10 303 628 166 120 6 45 857 922 27 638 752 444 975 70 982 578 786 335 913 219 967 968 267 96 330 104 767 412 612 703 388 247 312 833 880 715 233 270 380 660 212 103 801 944 898 783 991 836 176 640 12 253 229 605 790 875 749 252 978 465 900 124 791 770 72 790 759 94 241 33 550 22 329 773 612 421 658 557 289 616 609 682 452 962 983 818 675 547 843 98 135 492 731 581 328 994 426 726 22 603 261 449 354 338 24 688 158 957 526 491 69 675 948 155 195 393 635 469 19 232 622 710 815 209 165 59 463 172 623 271 55 341 540 848 259 456 850 100 774 710 812 682 961 281 906 408 241 112 895 398 929 72 328 67 803 880 789 345 131 329 334 983 927 612 632 992 597 849 531 206 648 468 525 990 967 822 283 517 462 437 16
样例输出
526397738