Chef and Segments

Chef has an array A consisting of N elements. He wants to find number of pairs of non-intersecting segments [a, b] and [c, d] (1 ≤ a ≤ b c ≤ d ≤ N) such there is no number that occurs in the subarray {Aa, Aa+1, ... , Ab} and {Ac, Ac+1, ... , Ad} simultaneously. Help Chef to find this number. Input - The first line of the input contains an integer T denoting the number of test cases. The desc