SEQFUN - Sequence Function

We define a sequence {x}: {x} = {x0, x1 ... xn-1 } where xi is an integer.

We have a function f: {x} → {x’} where {x} is a finite sequence.

After we have a finite sequence {x}, we can get f({x}) follow these rules :

  1. Remove all 0 in x : a 0 b 0 c d 0 e f 0 g → a b c d e f g
  2. Turn 1 into 100 and -1 into -100 : a 1 b 1 -1 c d e f g → a 100 b 100 -100 c d e f g
  3. Add all 2k (k>1) at the end of the sequence : a 2 b 8 c d e 1024 f g → a 2 b 8 c d e 1024 f g 2 8 1024
  4. Add any positive odd prime x at the end of the sequence x-1 times: a 3 b c 7 d e f 5 g → a 3 b c 7 d e f 5 g 3 3 7 7 7 7 7 7 5 5 5 5
  5. For any positive composite number (not 2k, k>1), we just keep it once: a 6 b 6 c d 6 e 4 4 f g → a 6 b c d e 4 4 f g
  6. Keep any t (t < -1) in the sequence.

For example:

  • {x} = {-5 1 0 2 9 16 7 5 3 2 9 9 -1}
  • f({x}) = {-5 100 2 9 16 7 5 3 2 -100 2 2 16 7 7 7 7 7 7 5 5 5 5 3 3}

We define g({x}) is the sum of all the element in sequence x.

We define h({x}) = g(f({x})) - g({x}).

A consecutive sequence of x is a sequence {xi, xi+1, xi+2 ... xj} where 0 ≤ i ≤ j < n.

Now I will give you a sequence {x}.

I want to ask you the maximal h({y}) where {y} is a consecutive sequence of {x}.

Input

One line consists one integer N, the length of {x}. (N ≤ 105, |xi| ≤ 10000)

Next N lines, each line consists one integer.

Output

The maximal h({y}) where {y} is a consecutive sequence of {x}. (|h({y})| ≤ 263-1)

Example

Input:
5
1
2
6
6
3

Output:
101

Added by:刘启鹏
Date:2010-06-08
Time limit:0.100s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS OBJC PERL6 SQLITE VB.NET
Resource:ALL41 CONTEST #2

hide comments
2010-09-07 12:02:12 [Rampage] Blue.Mary
A copy of my(or God Yang Zhe's) problem GSS2 :)

Last edit: 2010-09-07 12:02:35
2010-08-01 13:44:11 Ivan Katanic
1. it should be k > 0, instead of k > 1
2. rule(5) doesn't say 'not 100' as it say 'not 2^k'
2010-06-13 21:39:50 .:: Pratik ::.
f( {1,2,6,6,3} ) = {100,2,6,6,3,2,3,3}
Hence g({x}) = 125
g( {1,2,6,6,3} } = 18
Then isnt the answer = 107 for the sample case?

reply:
f( {1,2,6,6,3} ) = {100,2,6,3,2,3,3}
g(f({1,2,6,6,3}))=100+2+6+3+2+3+3=119
g({1,2,6,6,3})=18
h({1,2,6,6,3})=119-18=101

Got it
but i think this is wrong
a 6 b 6 c d 6 e 4 4 f g => a 6 b c d e 4 4 f g
must be
a 6 b 6 c d 6 e 4 4 f g => a 6 b c d e 4 f g

Reply:
(5). For any positive composite number (not 2^k, k>1 ), we just keep it once: a 6 b 6 c d 6 e 4 4 f g => a 6 b c d e 4 4 f g

Last edit: 2010-06-14 07:15:49
2010-06-12 18:15:13 Dominik Kempa
f({2 3 2 3}) = {2 3 2 3 2 2 3 3 3 3}
Is this true ?

Reply: yes

Last edit: 2010-06-12 23:38:47
2010-06-09 11:17:36 Oleg
f({1,2,6,6,3}) = {100,2,6,3,2,3,3} right ?
Why answer is 110 then ?

Reply: yes
Correction h({x}) = g(f({x}))-g({x})
and answer is 101

Last edit: 2010-06-09 11:16:19
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.