Taco Task Selection

You are given a list of tasks, each with an associated score representing its value. Your objective is to select a set of tasks such that no two consecutive tasks are chosen, and the sum of the selected tasks is maximized. Formally, given an array \(a_0, a_1, \dots, a_{n-1}\), find the maximum sum \(S\) achievable by selecting tasks with indices \(i_1, i_2, \dots, i_k\) that satisfy \(|i_j - i_{j+1}| \ge 2\) for all valid \(j\). For instance, if the list of tasks is [3, 2, 7, 10, 12], the optimal selection is 3, 7, and 12, resulting in a maximum sum of 22.

inputFormat

The input begins with an integer \(T\) denoting the number of test cases. Each test case is described as follows:

• The first line contains an integer \(n\), indicating the number of tasks.
• The second line contains \(n\) space-separated integers representing the scores of the tasks.

outputFormat

For each test case, output a single line containing the maximum score obtainable while ensuring that no two consecutively scheduled tasks are selected.

2
5
3 2 7 10 12
4
8 4 5 9

22
17