Untitled

package OT;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class BanBong {
	static int n, arr[], visit[], max;

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("Input.txt"));
		Scanner scanner = new Scanner(System.in);
		int tc = scanner.nextInt();
		for (int Case = 1; Case <= tc; Case++) {
			n = scanner.nextInt();
			arr = new int[n + 2];
			visit = new int[n + 2];
			for (int i = 1; i <= n; i++) {
				arr[i] = scanner.nextInt();
			}
			visit[0] = visit[n + 1] = 1;
			arr[0] = arr[n + 1] = 1;
			max = 0;
			backtrack(1, 0);
			System.out.println("Case #" + Case);
			System.out.println(max);

		}
	}

	static boolean check() {
		for (int i = 1; i <= n; i++) {
			if (visit[i] == 0) {
				return false;
			}
		}
		return true;
	}

	static int tong(int i) {
		int l = i - 1, r = i + 1;
		while (l > 0 && visit[l] != 0) {
			l--;
		}
		while (r <= n && visit[r] != 0) {
			r++;
		}
		if (visit[l] == 0 && visit[r] == 0) {
			return arr[l] * arr[r];
		}
		return arr[i];
	}

	private static void backtrack(int k, int sum) {

		if (check()) {
			max = sum > max ? sum : max;
			return;
		}

		for (int i = 1; i <= n; i++) {
			if (visit[i] == 0) {
				visit[i] = 1;
				backtrack(i + 1, sum + tong(i));
				visit[i] = 0;
			}

		}

	}
}