Maximize Difference Subarray

You are given an array of positive integers. Your task is to find a contiguous subarray that maximizes the value defined as the sum of its elements minus the number of distinct elements in the subarray. Formally, for a subarray with indices \(l\) to \(r\), you want to maximize

[ S = \left(\sum_{i=l}^{r} a_i\right) - \left|{a_l, a_{l+1}, \ldots, a_r}\right| ]

The answer should be reported as two 1-indexed numbers representing the starting and ending indices of this optimal subarray. If multiple subarrays achieve the maximum value, output the one that is found first using a sliding window strategy.

inputFormat

The first line contains an integer \(T\), the number of test cases. Each test case consists of two lines:

• The first line contains a single integer \(n\) – the length of the array.
• The second line contains \(n\) space-separated positive integers representing the array elements.

outputFormat

For each test case, print two space-separated integers \(l\) and \(r\) on a new line, where \(l\) and \(r\) are the 1-indexed starting and ending indices of the contiguous subarray that maximizes the value

[ \left(\sum_{i=l}^{r} a_i\right) - \left|{a_l, a_{l+1}, \ldots, a_r}\right| ]

sample

3
5
1 2 3 3 4
4
2 2 1 3
3
1 1 1

1 5
1 4
1 3