{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"A soap company wants to advertise their product in a local area. In this area, there are **n** houses and the houses are placed in circular fashion, such that house **1** has two neighbors: house **2** and **n**. House **5** has two neighbors: house **4** and **6**. House **n** has two neighbors, house **n-1** and **1**.\n\nNow the soap company has an estimation of the number of soaps they can sell on each house. But for their advertising policy, if they sell soaps to a house, they can\u0027t sell soaps to its two neighboring houses. No your task is to find the maximum number of estimated soaps they can sell in that area."}},{"title":"Input","value":{"format":"MD","content":"Input starts with an integer **T (\u0026le; 100)**, denoting the number of test cases.\n\nEach case starts with a line containing an integer **n (2 \u0026le; n \u0026le; 1000)**. The next line contains **n** space separated integers, where the **i\u003csup\u003eth\u003c/sup\u003e** integer denotes the estimated number of soaps that can be sold to the **i\u003csup\u003eth\u003c/sup\u003e** house. Each of these integers will lie in the range **[1, 1000]**."}},{"title":"Output","value":{"format":"MD","content":"For each case, print the case number and the maximum number of estimated soaps that can be sold in that area."}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3\n2\n10 100\n3\n10 2 11\n4\n8 9 2 8\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase 1: 100\nCase 2: 11\nCase 3: 17\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}