{"raw_statement":[{"iden":"statement","content":"Dzy and Fox have a sequence A consisting of N numbers [A1...AN]. Dzy starts by taking the first number, then Fox takes the second number, then Dzy takes the third number and so on, they continue taking turns until all of the N numbers are taken. The player with the highest sum of numbers wins.\n\nSince Dzy is your dear friend, you decided to rotate the sequence (you may rotate it as many times as you like) in order to maximize Dzy's sum of numbers.\n\nRotation is defined as removing the first element from the beginning of the sequence and adding it to the end of the sequence.\n\nSo given the sequence A , you have to help Dzy and let him achieve the maximum possible sum.\n\nThe first line containts a single integer T, the number of test cases.\n\nThen T testcases are given as follows :\n\nThe first line of each testcase contains a single integer N (1 ≤ n ≤ 104).\n\nThe second line of each testcase contains N space-separated integers [A1...AN],the elements of the sequence A (1 ≤ i ≤ n) ( - 109 ≤ Ai ≤ 109).\n\nOutput T lines , The answer for each testcase which is the maximum achievable sum by Dzy if you help him.\n\nConsider all 5 rotations of the sequence:\n\n_1 5 3 2 4_ (Dzy score = 1 + 3 + 4 = 8)\n\n_5 3 2 4 1_ (Dzy score = 8)\n\n_3 2 4 1 5_ (Dzy score = 12)\n\n_2 4 1 5 3_ (Dzy score = 6)\n\n_4 1 5 3 2_ (Dzy score = 11)\n\n"},{"iden":"input","content":"The first line containts a single integer T, the number of test cases.Then T testcases are given as follows :The first line of each testcase contains a single integer N (1 ≤ n ≤ 104).The second line of each testcase contains N space-separated integers [A1...AN],the elements of the sequence A (1 ≤ i ≤ n) ( - 109 ≤ Ai ≤ 109)."},{"iden":"output","content":"Output T lines , The answer for each testcase which is the maximum achievable sum by Dzy if you help him."},{"iden":"examples","content":"Input151 5 3 2 4Output12"},{"iden":"note","content":"Consider all 5 rotations of the sequence:_1 5 3 2 4_ (Dzy score = 1 + 3 + 4 = 8)_5 3 2 4 1_ (Dzy score = 8)_3 2 4 1 5_ (Dzy score = 12)_2 4 1 5 3_ (Dzy score = 6)_4 1 5 3 2_ (Dzy score = 11)"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case $ k \\in \\{1, \\dots, T\\} $:  \n- Let $ n_k \\in \\mathbb{Z} $ denote the length of the sequence.  \n- Let $ A_k = (a_{k,1}, a_{k,2}, \\dots, a_{k,n_k}) $ be a sequence of integers.  \n\n**Constraints**  \n1. $ 1 \\le T \\le \\text{unbounded} $ (implied by input format)  \n2. For each $ k \\in \\{1, \\dots, T\\} $:  \n   - $ 1 \\le n_k \\le 10^4 $  \n   - $ -10^9 \\le a_{k,i} \\le 10^9 $ for all $ i \\in \\{1, \\dots, n_k\\} $  \n\n**Objective**  \nFor each test case $ k $, consider all $ n_k $ cyclic rotations of $ A_k $.  \nFor a rotation starting at index $ r \\in \\{0, \\dots, n_k - 1\\} $, the resulting sequence is:  \n$$\nA_k^{(r)} = (a_{k, r+1}, a_{k, r+2}, \\dots, a_{k, n_k}, a_{k,1}, \\dots, a_{k,r})\n$$  \nDzy picks elements at odd positions (1st, 3rd, 5th, ...) in $ A_k^{(r)} $.  \nDefine Dzy’s sum for rotation $ r $ as:  \n$$\nS_k(r) = \\sum_{\\substack{i=1 \\\\ i \\text{ odd}}}^{n_k} a_{k, ((r + i - 1) \\bmod n_k) + 1}\n$$  \nCompute:  \n$$\n\\max_{r \\in \\{0, \\dots, n_k - 1\\}} S_k(r)\n$$","simple_statement":"You are given a sequence of N numbers. Dzy and Fox take turns picking numbers: Dzy picks first, then Fox, then Dzy, and so on. Dzy gets the 1st, 3rd, 5th, ... numbers. You can rotate the sequence any number of times (move first element to the end). Find the maximum sum Dzy can get over all possible rotations.","has_page_source":false}