INSULENG - Insulation

no tags 

Give N bricks and a sequence a1...an as the insulation of them. If we arrange the bricks in that order into a wall then the insulation of the wall is a1 + a2 + ... + aN + max(0, a2 - a1) + max(0, a3 - a2) + ... + max(0, aN - aN - 1). Your task is to arrange the bricks so that the insulation of the wall is maximum.

Input

  • The first line is N (1 <= N <= 105).
  • In each of the next N lines, the ith line is ai-1

Output

  • The maximum insulation of the wall.

Example

Input:
4
5
4
1
7 Output:
24

hide comments
Mitch Schwartz: 2011-11-04 03:45:54

Input is poorly formatted.

Egor: 2011-03-18 13:26:03

greed!

:D: 2011-03-15 11:08:16

I think this problems is set as a challenge (my score for challenges isn't adding up). Please correct that.

T-7: 2011-03-15 07:56:05

The example is 24 if we arrange the bricks like this: 1 5 4 7 ;)

Eduardo Carrasquero: 2011-03-15 04:53:07

the example is 23 for me...
5+4+1+7 = 17
0+0+6 = 6
= 23
What am I doing wrong?

cegprakash: 2011-03-14 17:53:38

i think such test cases went for me to TLE
and thats y i'm getting low score.. any hint to find that possibility?

:D: 2011-03-14 17:25:44

How did you checked all permutations for N=10^5 :O

Sushovan Sen: 2011-03-14 17:08:05

I dont understand scoring..

Kashyap Krishnakumar: 2011-03-14 15:53:22

@cegprakash: you need not check for all permutations! :P


Added by:Hacker7
Date:2011-03-14
Time limit:0.200s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:ADA95 ASM32 BASH BF C CSHARP C++ 4.3.2 CPP C99 CLPS CLOJURE LISP sbcl LISP clisp D ERL FSHARP FORTRAN GO HASK ICON ICK JAVA JS-RHINO LUA NEM NICE OCAML PAS-GPC PAS-FPC PERL PERL6 PHP PIKE PRLG-swi PYTHON PYTHON3 RUBY SCALA SCM guile SCM qobi ST TCL WHITESPACE
Resource:VNOI