import java.util.Scanner;
 
public class Main {
 
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();  // Number of test cases
 
        while (t-- > 0) {
            int n = scanner.nextInt();  // Number of contests
            int[] a = new int[n];  // Ratings of contests
 
            // Read contest ratings
            for (int i = 0; i < n; i++) {
                a[i] = scanner.nextInt();
            }
 
            // Calculate and print the result for each test case
            System.out.println(maximizeRating(n, a));
        }
 
        scanner.close();
    }
 
    private static int maximizeRating(int n, int[] a) {
        // Step 1: Calculate the initial rating x
        int x = 0;
        for (int i = 0; i < n; i++) {
            if (a[i] > x) {
                x++;
            } else if (a[i] < x) {
                x--;
            }
        }
 
        // Step 2: Calculate the gain array based on the contest ratings
        int[] gain = new int[n];
        for (int i = 0; i < n; i++) {
            if (a[i] > x) {
                gain[i] = -1;  // Loss (if we consider this contest)
            } else if (a[i] < x) {
                gain[i] = 1;   // Gain (if we consider this contest)
            } else {
                gain[i] = 0;   // No change (if we consider this contest)
            }
        }
 
        // Step 3: Apply Kadane's algorithm to find the maximum subarray sum (optimal interval to skip)
        int maxGain = Integer.MIN_VALUE;    // Max gain from skipping a subarray
        int currentMax = 0; // Current sum while traversing the array
 
        for (int i = 0; i < n; i++) {
            currentMax = Math.max(gain[i], currentMax + gain[i]); // Kadane's logic
            maxGain = Math.max(maxGain, currentMax);  // Update the maximum gain
        }
 
        // Step 4: Return the initial rating + the maximum gain from skipping an optimal subarray
        return x + maxGain;
    }
}
 

aW1wb3J0IGphdmEudXRpbC5TY2FubmVyOwoKcHVibGljIGNsYXNzIE1haW4gewoKICAgIHB1YmxpYyBzdGF0aWMgdm9pZCBtYWluKFN0cmluZ1tdIGFyZ3MpIHsKICAgICAgICBTY2FubmVyIHNjYW5uZXIgPSBuZXcgU2Nhbm5lcihTeXN0ZW0uaW4pOwogICAgICAgIGludCB0ID0gc2Nhbm5lci5uZXh0SW50KCk7ICAvLyBOdW1iZXIgb2YgdGVzdCBjYXNlcwogICAgICAgIAogICAgICAgIHdoaWxlICh0LS0gPiAwKSB7CiAgICAgICAgICAgIGludCBuID0gc2Nhbm5lci5uZXh0SW50KCk7ICAvLyBOdW1iZXIgb2YgY29udGVzdHMKICAgICAgICAgICAgaW50W10gYSA9IG5ldyBpbnRbbl07ICAvLyBSYXRpbmdzIG9mIGNvbnRlc3RzCiAgICAgICAgICAgIAogICAgICAgICAgICAvLyBSZWFkIGNvbnRlc3QgcmF0aW5ncwogICAgICAgICAgICBmb3IgKGludCBpID0gMDsgaSA8IG47IGkrKykgewogICAgICAgICAgICAgICAgYVtpXSA9IHNjYW5uZXIubmV4dEludCgpOwogICAgICAgICAgICB9CgogICAgICAgICAgICAvLyBDYWxjdWxhdGUgYW5kIHByaW50IHRoZSByZXN1bHQgZm9yIGVhY2ggdGVzdCBjYXNlCiAgICAgICAgICAgIFN5c3RlbS5vdXQucHJpbnRsbihtYXhpbWl6ZVJhdGluZyhuLCBhKSk7CiAgICAgICAgfQogICAgICAgIAogICAgICAgIHNjYW5uZXIuY2xvc2UoKTsKICAgIH0KCiAgICBwcml2YXRlIHN0YXRpYyBpbnQgbWF4aW1pemVSYXRpbmcoaW50IG4sIGludFtdIGEpIHsKICAgICAgICAvLyBTdGVwIDE6IENhbGN1bGF0ZSB0aGUgaW5pdGlhbCByYXRpbmcgeAogICAgICAgIGludCB4ID0gMDsKICAgICAgICBmb3IgKGludCBpID0gMDsgaSA8IG47IGkrKykgewogICAgICAgICAgICBpZiAoYVtpXSA+IHgpIHsKICAgICAgICAgICAgICAgIHgrKzsKICAgICAgICAgICAgfSBlbHNlIGlmIChhW2ldIDwgeCkgewogICAgICAgICAgICAgICAgeC0tOwogICAgICAgICAgICB9CiAgICAgICAgfQoKICAgICAgICAvLyBTdGVwIDI6IENhbGN1bGF0ZSB0aGUgZ2FpbiBhcnJheSBiYXNlZCBvbiB0aGUgY29udGVzdCByYXRpbmdzCiAgICAgICAgaW50W10gZ2FpbiA9IG5ldyBpbnRbbl07CiAgICAgICAgZm9yIChpbnQgaSA9IDA7IGkgPCBuOyBpKyspIHsKICAgICAgICAgICAgaWYgKGFbaV0gPiB4KSB7CiAgICAgICAgICAgICAgICBnYWluW2ldID0gLTE7ICAvLyBMb3NzIChpZiB3ZSBjb25zaWRlciB0aGlzIGNvbnRlc3QpCiAgICAgICAgICAgIH0gZWxzZSBpZiAoYVtpXSA8IHgpIHsKICAgICAgICAgICAgICAgIGdhaW5baV0gPSAxOyAgIC8vIEdhaW4gKGlmIHdlIGNvbnNpZGVyIHRoaXMgY29udGVzdCkKICAgICAgICAgICAgfSBlbHNlIHsKICAgICAgICAgICAgICAgIGdhaW5baV0gPSAwOyAgIC8vIE5vIGNoYW5nZSAoaWYgd2UgY29uc2lkZXIgdGhpcyBjb250ZXN0KQogICAgICAgICAgICB9CiAgICAgICAgfQoKICAgICAgICAvLyBTdGVwIDM6IEFwcGx5IEthZGFuZSdzIGFsZ29yaXRobSB0byBmaW5kIHRoZSBtYXhpbXVtIHN1YmFycmF5IHN1bSAob3B0aW1hbCBpbnRlcnZhbCB0byBza2lwKQogICAgICAgIGludCBtYXhHYWluID0gSW50ZWdlci5NSU5fVkFMVUU7ICAgIC8vIE1heCBnYWluIGZyb20gc2tpcHBpbmcgYSBzdWJhcnJheQogICAgICAgIGludCBjdXJyZW50TWF4ID0gMDsgLy8gQ3VycmVudCBzdW0gd2hpbGUgdHJhdmVyc2luZyB0aGUgYXJyYXkKCiAgICAgICAgZm9yIChpbnQgaSA9IDA7IGkgPCBuOyBpKyspIHsKICAgICAgICAgICAgY3VycmVudE1heCA9IE1hdGgubWF4KGdhaW5baV0sIGN1cnJlbnRNYXggKyBnYWluW2ldKTsgLy8gS2FkYW5lJ3MgbG9naWMKICAgICAgICAgICAgbWF4R2FpbiA9IE1hdGgubWF4KG1heEdhaW4sIGN1cnJlbnRNYXgpOyAgLy8gVXBkYXRlIHRoZSBtYXhpbXVtIGdhaW4KICAgICAgICB9CgogICAgICAgIC8vIFN0ZXAgNDogUmV0dXJuIHRoZSBpbml0aWFsIHJhdGluZyArIHRoZSBtYXhpbXVtIGdhaW4gZnJvbSBza2lwcGluZyBhbiBvcHRpbWFsIHN1YmFycmF5CiAgICAgICAgcmV0dXJuIHggKyBtYXhHYWluOwogICAgfQp9Cg==

NQo2CjEgMiAzIDQgNSA2CjcKMSAyIDEgMSAxIDMgNAoxCjEKOQo5IDkgOCAyIDQgNCAzIDUgMwoxMAoxIDIgMyA0IDEgMyAyIDEgMSAxMAo=

5
6
1 2 3 4 5 6
7
1 2 1 1 1 3 4
1
1
9
9 9 8 2 4 4 3 5 3
10
1 2 3 4 1 3 2 1 1 10