Once upon a time Petya and Gena gathered after another programming competition and decided to play some game. As they consider most modern games to be boring, they always try to invent their own games. They have only stickers and markers, but that won't stop them.

The game they came up with has the following rules. Initially, there are *n* stickers on the wall arranged in a row. Each sticker has some number written on it. Now they alternate turn, Petya moves first.

One move happens as follows. Lets say there are *m* ≥ 2 stickers on the wall. The player, who makes the current move, picks some integer *k* from 2 to *m* and takes *k* leftmost stickers (removes them from the wall). After that he makes the new sticker, puts it to the left end of the row, and writes on it the new integer, equal to the sum of all stickers he took on this move. 

Game ends when there is only one sticker left on the wall. The score of the player is equal to the sum of integers written on all stickers he took during all his moves. The goal of each player is to maximize the difference between his score and the score of his opponent.

Given the integer *n* and the initial sequence of stickers on the wall, define the result of the game, i.e. the difference between the Petya's and Gena's score if both players play optimally.
The first line of input contains a single integer *n* (2 ≤ *n* ≤ 200 000) — the number of stickers, initially located on the wall.

The second line contains *n* integers *a*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">2</sub>, ..., *a*<sub class="lower-index">*n*</sub> ( - 10 000 ≤ *a*<sub class="lower-index">*i*</sub> ≤ 10 000) — the numbers on stickers in order from left to right.
In the first sample, the optimal move for Petya is to take all the stickers. As a result, his score will be equal to 14 and Gena's score will be equal to 0.

In the second sample, the optimal sequence of moves is the following. On the first move Petya will take first three sticker and will put the new sticker with value  - 8. On the second move Gena will take the remaining two stickers. The Petya's score is 1 + ( - 7) + ( - 2) =  - 8, Gena's score is ( - 8) + 3 =  - 5, i.e. the score difference will be  - 3.
3
2 4 8
14
4
1 -7 -2 3
-3
10
35 11 35 28 48 25 2 43 23 10
260
100
437 89 481 95 29 326 10 304 97 414 52 46 106 181 385 173 337 148 437 133 52 136 86 250 289 61 480 314 166 69 275 486 117 129 353 412 382 469 290 479 388 231 7 462 247 432 488 146 466 422 369 336 148 460 418 356 303 149 421 146 233 224 432 239 392 409 172 331 152 433 345 205 451 138 273 284 48 109 294 281 468 301 337 176 137 52 216 79 431 141 147 240 107 184 393 459 286 123 297 160
26149
3
2 1 2
5
101
11 -250 -200 157 84 89 207 139 -76 -183 -26 -218 79 -122 244 -133 82 -64 38 131 184 -154 256 -250 -246 227 -57 -188 -208 -48 64 -163 213 -110 -17 -106 -96 198 19 -214 50 -117 -215 214 -254 185 -7 19 117 112 172 -229 66 -169 209 -110 122 223 0 -151 66 -154 20 77 -180 202 246 -209 24 -180 -3 10 -86 -26 50 29 225 47 -177 225 -189 -40 -114 -56 -50 70 -102 160 -26 167 48 188 -84 -194 -201 250 135 -174 -222 192 -64
211
102
-70 -76 15 -32 -88 -26 75 23 92 -96 7 34 92 45 -62 -90 -26 78 -11 -63 34 -61 54 -32 -63 -70 38 73 22 97 -67 81 76 -10 -90 23 47 -23 31 25 -68 75 33 -71 95 57 -9 38 -22 39 68 -19 29 -67 41 75 13 36 5 3 -4 9 -9 -42 -72 51 -44 67 55 -1 30 -1 -9 101 39 -80 86 50 78 -81 11 -19 -63 72 -82 54 -18 -5 -101 22 50 3 26 -52 -83 -21 -9 -54 86 12 -21 99
487
103
-26 87 -179 -82 156 68 -131 67 -203 166 -6 -3 99 176 97 -115 73 155 30 208 131 -106 -20 98 -77 -60 -152 -24 -158 185 193 112 86 -74 114 -185 49 162 -207 96 -70 -212 12 28 -19 73 -115 -169 169 -27 -183 112 -207 112 42 -107 31 -92 161 -84 181 21 189 190 -115 54 -138 140 169 161 -197 146 -25 44 95 -121 -19 -180 -5 172 -81 -51 -86 137 27 -152 17 -121 -177 113 94 -179 -11 -38 201 -155 -22 -104 -21 161 189 -60 115
813
104
256 256 256 256 256 256 256 256 256 256 256 256 256 256 256 256 256 256 256 256 256 256 256 256 256 256 256 256 256 256 256 256 256 256 256 256 256 256 256 256 256 256 256 256 256 256 256 256 256 256 256 256 256 256 256 256 256 256 256 256 256 256 256 256 256 256 256 256 256 256 256 256 256 256 256 256 256 256 256 256 256 256 256 256 256 256 256 256 256 256 256 256 256 256 256 256 256 256 256 256 256 256 256 256
26624
105
102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102
10710
106
212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212 212
22472
107
256 -256 256 -256 256 -256 256 -256 256 -256 256 -256 256 -256 256 -256 256 -256 256 -256 256 -256 256 -256 256 -256 256 -256 256 -256 256 -256 256 -256 256 -256 256 -256 256 -256 256 -256 256 -256 256 -256 256 -256 256 -256 256 -256 256 -256 256 -256 256 -256 256 -256 256 -256 256 -256 256 -256 256 -256 256 -256 256 -256 256 -256 256 -256 256 -256 256 -256 256 -256 256 -256 256 -256 256 -256 256 -256 256 -256 256 -256 256 -256 256 -256 256 -256 256 -256 256 -256 256 -256 256
256
108
102 -102 102 -102 102 -102 102 -102 102 -102 102 -102 102 -102 102 -102 102 -102 102 -102 102 -102 102 -102 102 -102 102 -102 102 -102 102 -102 102 -102 102 -102 102 -102 102 -102 102 -102 102 -102 102 -102 102 -102 102 -102 102 -102 102 -102 102 -102 102 -102 102 -102 102 -102 102 -102 102 -102 102 -102 102 -102 102 -102 102 -102 102 -102 102 -102 102 -102 102 -102 102 -102 102 -102 102 -102 102 -102 102 -102 102 -102 102 -102 102 -102 102 -102 102 -102 102 -102 102 -102 102 -102
102
109
212 -212 212 -212 212 -212 212 -212 212 -212 212 -212 212 -212 212 -212 212 -212 212 -212 212 -212 212 -212 212 -212 212 -212 212 -212 212 -212 212 -212 212 -212 212 -212 212 -212 212 -212 212 -212 212 -212 212 -212 212 -212 212 -212 212 -212 212 -212 212 -212 212 -212 212 -212 212 -212 212 -212 212 -212 212 -212 212 -212 212 -212 212 -212 212 -212 212 -212 212 -212 212 -212 212 -212 212 -212 212 -212 212 -212 212 -212 212 -212 212 -212 212 -212 212 -212 212 -212 212 -212 212 -212 212
212
110
-256 -149 -136 -33 -253 -141 -170 -253 0 -107 -141 -236 -65 -158 -84 -180 -97 -97 -223 -44 -232 -255 -108 -25 -49 -48 -212 -3 -232 -172 -231 -158 -23 -206 -198 -55 -36 -11 -169 -94 -190 -115 -116 -231 -155 -201 -155 -103 -242 -119 -136 -8 -2 -11 -69 -250 -51 -129 -155 -216 -107 -102 -186 -13 -78 -2 -238 -66 -29 -102 -249 -198 -151 -38 -3 -128 -130 -73 -236 -83 -28 -95 -140 -62 -24 -168 -199 -196 -28 -28 -6 -220 -247 -75 -200 -228 -109 -251 -76 -53 -43 -170 -213 -146 -68 -58 -58 -218 -186 -165
165
111
-66 -39 -25 -78 -75 -44 -56 -89 -70 -7 -46 -70 -51 -36 -61 -95 -40 -84 -48 -8 -35 -37 -47 -35 -75 -87 -10 -101 -43 -70 -28 -50 -39 -13 -34 -40 -100 -70 -32 -12 -23 -62 -41 -94 -25 -30 -102 -32 -78 -10 -82 -71 -34 -2 -100 -60 -14 -17 -12 -57 -96 -27 -27 -23 -74 -60 -30 -38 -61 -95 -41 -73 -24 -76 -68 -29 -17 -75 -28 -86 -68 -25 -20 -68 -100 -44 -47 -8 -85 -84 -68 -92 -33 -9 -40 -83 -64 -2 -94 -66 -65 -46 -22 -41 -47 -24 -56 -91 -65 -63 -5
5
113
154 110 128 156 88 54 172 96 93 13 108 219 37 34 44 153 73 23 0 210 85 18 243 147 174 182 153 196 200 223 162 151 237 148 174 86 181 1 17 187 81 175 46 253 131 44 145 184 53 164 97 220 94 0 8 157 225 50 90 186 79 67 199 108 159 86 173 181 208 182 17 254 82 61 64 7 29 112 156 105 175 91 165 229 162 101 3 62 154 32 13 133 116 185 237 94 67 171 23 123 249 255 135 23 126 115 175 73 128 16 88 139 78
13598
114
46 7 39 21 44 31 49 57 26 22 86 45 66 72 96 15 77 38 92 88 50 68 30 55 20 5 15 11 26 66 94 74 43 73 35 7 11 36 26 74 86 52 14 5 91 71 3 75 22 7 10 97 42 41 52 80 97 31 45 59 53 85 87 63 42 51 98 61 26 96 65 22 47 0 36 27 35 69 81 58 9 43 7 98 27 56 101 2 31 82 48 100 77 77 42 61 6 32 69 30 102 64 51 64 20 24 76 87 63 52 73 41 5 34
5672
115
176 163 163 37 7 157 82 29 153 189 174 103 105 90 49 63 88 151 198 31 178 110 15 188 20 181 167 118 133 203 121 150 201 103 205 160 103 91 177 133 107 147 11 11 199 137 139 153 29 94 81 143 185 137 101 71 26 14 123 73 72 134 149 51 175 71 41 155 111 146 61 140 82 75 134 107 142 95 159 132 5 76 32 133 71 129 207 212 77 173 185 123 174 53 88 44 105 37 115 204 172 4 207 118 28 134 207 50 194 40 54 95 47 39 70
12880
2
-10000 -10000
-20000
4
2 -10000 -10 4
-4
6
-6000 -5000 -4000 -3000 -2000 -1000
1000
10
-10000 -10000 100 100 100 100 100 100 100 100
-100
2
1313 8442
9755
2
5 -3
2
4
1 5 -6 0
6
import sys
input = sys.stdin.buffer.readline 

def process(A):
    n = len(A)
    S = [0]
    for i in range(n):
        S.append(S[-1]+A[i])
    d = [None for i in range(n)]
    d[-1] = S[-1]
    my_max = d[-1]
    my_min = d[-1]
    for i in range(n-2, -1, -1):
        fi = d[i+1]
        my_max = max(S[i+1]-fi, my_max)
        d[i] = my_max
    return max(d[1:])

n = int(input())
A = [int(x) for x in input().split()]
print(process(A))