Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Heart of the Demon

By ShouravAhmed · Limits 1s, 512 MB

“The weak have no rights or choices. Their only fate is to be relentlessly crushed by the strong!” – Giyu Tomioka

Muzan Kibutsuji is the Demon King, the first of his kind, as a being who has lived over thousands of years he becomes unimaginably strong with capabilities, he killed an innumerable number of people and turned some of them into Demon.

Since ancient times, the “Demon Slayer Corps” has existed to hunt down Demons. They are number in the hundreds, an organization completely unrecognized by the government.

In one demon attack, the full family of Tanjiro Kamado was destroyed, now the goal of his life is to kill Muzan to avenge his family. After years of extreme training in “Demon Slayer” finally he is ready to fight with Muzan.

Tanjiro finds out that Muzan can't be killed like other demons. The heart of Muzan is divided into NN parts and placed in secret places with very strong protection. To kill Muzan, Tanjiro needs to collect all the parts of the heart and marge them all together, and stab in the middle of the heart with his sword.

All the parts of the heart are of a distinctdistinct size so each part of the heart can be represented with its size which is an integer number. If the heart is {7,5,3,11,27,5,3,11,2} then to find the middle of the heart he has to find all the parts and marge them in increasing order like {2,3,5,7,112, 3, 5, 7, 11}. Here the middle element is the middle of the heart which is 5.

Now, Tanjiro knows how to kill Muzan but if he fails there will be no other chance to kill Muzan in a thousand years.  So, before the attack, Tanjiro needs to know how much stamina he needs to marge the heart and what is the middle of the heart.

The stamina he needs to find all the parts and marge them, for this heart {7,5,3,11,27,5,3,11,2} is 77
Let’s see how to calculate it,
What Tanjiro will do in each of his moves is, find the smallest part of the heart and take it, the stamina he needs for taking the part is the number of remaining parts in its left.
If the Heart is: {7,5,3,11,27, 5, 3, 11, 2}

Move-0: [{}: {7,5,3,11,27, 5, 3, 11, 2}] [starting the attack]
Move-1: [{22}: {7,5,3,117, 5, 3, 11}] [Takes the part 2 and stamina used is 4]
Move-2: [{2,32, 3}: {7,5,117, 5, 11}] [Takes the part 3 and stamina used is 2]
Move-3: [{2,3,52, 3, 5}: {7,117, 11}] [Takes the part 5 and stamina used is 1]
Move-4: [{2,3,5,72, 3, 5, 7}: {1111}] [Takes the part 7 and stamina used is 0]
Move-5: [{2,3,5,7,112, 3, 5, 7, 11}: {}] [Takes the part 11 and stamina used is 0]

So, to marge this heart total stamina needed is (4+2+1+0+0)=7(4 + 2 + 1 + 0 + 0) = 7 and the middle of the heart is 55.

Tanjiro performs best at fighting but struggles with math, so he needs assistance.
Now, as you are the best thinker of the Demon Slayer Corps, you have to find the stamina needed to marge the given heart and the middle of that heart.

Input

The first line of the input will contain a single integer NN the number of the parts of the Heart. It is grunted that N is always a positive odd number and 0<N<1060 < N < 10^{6}. The next line will contain N integers where each of them is representing a part of the heart 1hi1091 \leq h_{i}\leq 10^{9}.

Output

For the given information of the Heart, you have to output a single line with two integer total stamina and the middle of the heart.

Samples

InputOutput
5
7 5 3 11 2
7 5
InputOutput
7
1 2 3 4 5 6 7
0 4

Dataset is huge, use faster I/O methods.

    Discussion

    Statistics


    42% Solution Ratio

    MursaleenEarliest, 1w ago

    n3wb13_223Fastest, 0.2s

    steinumLightest, 8.1 MB

    steinumShortest, 592B

    Submit

    Login to submit

    Editorial

    From the problem statement, we know in each step we need to remove the smallest element from the rem...