<s> """<STR_LIT>""" <EOL> __author__ = '<STR_LIT>' <EOL> class Solution ( object ) : <EOL> def solve ( self , cipher ) : <EOL> """<STR_LIT>""" <EOL> N , v = cipher <EOL> v . reverse ( ) <EOL> s = [ <NUM_LIT:0> for _ in xrange ( N + <NUM_LIT:1> ) ] <EOL> for i in xrange ( <NUM_LIT:1> , N + <NUM_LIT:1> ) : <EOL> s [ i ] = s [ i - <NUM_LIT:1> ] + v [ i - <NUM_LIT:1> ] <EOL> f = [ [ <NUM_LIT:0> , <NUM_LIT:0> ] for _ in xrange ( N + <NUM_LIT:1> ) ] <EOL> for i in xrange ( <NUM_LIT:1> , N + <NUM_LIT:1> ) : <EOL> local_max = <NUM_LIT:0> <EOL> for k in xrange ( <NUM_LIT:1> , <NUM_LIT:4> ) : <EOL> if i - k >= <NUM_LIT:0> : <EOL> local_max = max ( local_max , s [ i ] - s [ i - k ] + s [ i - k ] - f [ i - k ] [ <NUM_LIT:1> ] ) <EOL> f [ i ] [ <NUM_LIT:0> ] = local_max <EOL> local_max = <NUM_LIT:0> <EOL> for k in xrange ( <NUM_LIT:1> , <NUM_LIT:4> ) : <EOL> if i - k >= <NUM_LIT:0> : <EOL> local_max = max ( local_max , s [ i ] - s [ i - k ] + s [ i - k ] - f [ i - k ] [ <NUM_LIT:0> ] ) <EOL> f [ i ] [ <NUM_LIT:1> ] = local_max <EOL> return f [ - <NUM_LIT:1> ] [ <NUM_LIT:0> ] <EOL> if __name__ == "<STR_LIT:__main__>" : <EOL> import sys <EOL> f = open ( "<STR_LIT>" , "<STR_LIT:r>" ) <EOL> testcases = int ( f . readline ( ) . strip ( ) ) <EOL> for t in xrange ( testcases ) : <EOL> N = int ( f . readline ( ) . strip ( ) ) <EOL> lst = map ( lambda x : int ( x ) , f . readline ( ) . strip ( ) . split ( "<STR_LIT:U+0020>" ) ) <EOL> cipher = [ N , lst ] <EOL> s = "<STR_LIT>" % ( Solution ( ) . solve ( cipher ) ) <EOL> print s , </s>
