{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"Wavio is a sequence of integers. It has some interesting properties:\n\n1. Wavio is of odd length i.e. **L \u003d 2\\*n + 1**.\n2. The first **(n+1)** integers of Wavio sequence make a strictly increasing sequence.\n3. The last **(n+1)** integers of Wavio sequence make a strictly decreasing sequence.\n4. No two adjacent integers are same in a Wavio sequence.\n\nFor example `{1, 2, 3, 4, 5, 4, 3, 2, 1}` is an Wavio sequence of length **9**. But `{1, 2, 3, 4, 5, 4, 3, 2, 2}` is not a valid wavio sequence.\n\nIn this problem, you will be given a sequence of integers. You have to find the length of the longest Wavio sequence which is a **subsequence** of the given sequence. For the given sequence: `{1, 2, 3, 2, 1, 2, 3, 4, 3, 2, 1, 5, 4, 1, 2, 3, 2, 2, 1}` the longest Wavio sequence is: `{1, 2, 3, 4, 5, 4, 3, 2, 1}`. Thus, the result should be be **9**."}},{"title":"Input","value":{"format":"MD","content":"Input starts with an integer **T (\u0026le; 12)**, denoting the number of test cases.\n\nEach case starts with a line containing an integer **N (1 \u0026le; N \u0026le; 10\u003csup\u003e5\u003c/sup\u003e)** denoting the number of elements in the sequence. The next line contains **N** space separated integers between **-10\u003csup\u003e8\u003c/sup\u003e** to **10\u003csup\u003e8\u003c/sup\u003e**, that form the sequence."}},{"title":"Output","value":{"format":"MD","content":"For each case, print the case number and the length of the maximum possible Wavio sequence."}},{"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\n10\n1 2 3 4 5 4 3 2 1 10\n14\n1 2 3 2 1 2 3 4 3 2 1 5 4 1\n5\n1 2 3 4 5\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase 1: 9\nCase 2: 7\nCase 3: 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"MD","content":"Dataset is huge, use faster I/O methods."}}]}