INSULENG - Insulation

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

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

hide comments
2011-03-14 15:31:08 cegprakash
i've checked all the permutations. still i'm not getting 100.
2011-03-14 14:21:06 Pranay
scoring is as like partial?

Last edit: 2011-03-14 14:21:52
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.