Maximum Sum Triplet Indices

You are given an array of integers. Your task is to choose three indices i, j, and k such that \(0 \le i < j < k < n\) (where \(n\) is the length of the array) and the sum arr[i] + arr[j] + arr[k] is maximized.

If the array length is less than 3, output should be 'None None None'. Otherwise, output the indices of the triplet which gives the maximum sum. In case of multiple answers, output the one found first by the brute-force method.

Note: The constraints are small enough to allow a solution with \(O(n^3)\) time complexity.

inputFormat

The first line contains an integer \(n\) denoting the number of elements in the array. The second line contains \(n\) space-separated integers representing the elements of the array.

outputFormat

Output three space-separated integers representing the indices that yield the maximum sum triplet. If \(n < 3\), output None None None.

5
2 6 1 4 9

1 3 4