CF 2019A - Max Plus Size

给你一个正整数数组 a1,a2,...,ana1,a2,...,an。

你可以将数组中的一些元素涂成红色，但不能有两个相邻的红色元素（即对于 1≤i≤n-11≤i≤n-1 的数组，aii 和 ai+1ai+1 中至少有一个元素不能是红色的）。

你的得分是红色元素的最大值加上红色元素的数量。找出你能得到的最大分数。

输入

每个测试包含多个测试用例。第一行包含测试用例数 tt（1≤t≤5001≤t≤500）。测试用例说明如下。

每个测试用例的第一行包含一个整数 nn（1≤n≤1001≤n≤100）--数组的长度。

每个测试用例的第二行包含 nn 个整数 a1,a2,...,ana1,a2,...,an（1≤ai≤10001≤ai≤1000）--给定的数组。

输出

对于每个测试用例，输出一个整数：根据声明将某些元素染成红色后可能得到的最大分数。

示例

------------

dp,保存三种状态，然后我居然直接就过了。。