Doremy has n buckets of paint which is represented by an array a of length n. Bucket i contains paint with color ai. Let c(l,r) be the number of distinct elements in the subarray [al,al+1,…,ar]. Choose 2 integers l and r such that l≤r and r−l−c(l,r) is maximized. Input The input consists of multiple test cases. The first line contains a single integer t (1≤t≤104) — the number of test cases. The description of the test cases follows. The first line of each test case contains a single integer n (1≤n≤105) — the length of the array a. The second line of each test case contains n integers a1,a2,…,an (1≤ai≤n). It is guaranteed that the sum of n does not exceed 105.

这道题目的意思是说，有一个长度为 n 的数组 a，数组的第 i 个位置上的数表示第 i 个桶中油漆的颜色。对于给定的 l 和 r，c(l,r) 表示区间 [l,r] 中不同颜色的数量。你需要选择两个整数 l 和 r，使得 l≤r 且 r−l−c(l,r) 最大。输入包含多组测试数据。第一行包含一个整数 t，表示测试数据组数。接下来每组测试数据包含两行，第一行包含一个整数 n，表示数组 a 的长度；第二行包含 n 个整数 a1,a2,…,an，表示数组 a。保证 n 的总和不超过 105。