java
import java.util.*;
import java.lang.*;
import java.io.*;

class Codechef {
	
    // Fast IO helper
    static class FastReader {
        final private int BUFFER_SIZE = 1 << 16;
        private DataInputStream din;
        private byte[] buffer;
        private int bufferPointer, bytesRead;
        
        public FastReader() {
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }
        
        public FastReader(String file_name) throws IOException {
            din = new DataInputStream(new FileInputStream(file_name));
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }
        
        public String nextLine() throws IOException {
            byte[] buf = new byte[100000]; // string length
            int cnt = 0, c;
            while ((c = read()) != -1) {
                if (c == '\n') {
                    if (cnt != 0) break;
                    else continue;
                }
                buf[cnt++] = (byte) c;
            }
            return new String(buf, 0, cnt);
        }
        
        public int nextInt() throws IOException {
            int ret = 0;
            byte c = read();
            while (c <= ' ') c = read();
            boolean neg = (c == '-');
            if (neg) c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
            if (neg) return -ret;
            return ret;
        }
        
        public long nextLong() throws IOException {
            long ret = 0;
            byte c = read();
            while (c <= ' ') c = read();
            boolean neg = (c == '-');
            if (neg) c = read();
            do {
                ret = ret * 10 + c - '0';
            }
            while ((c = read()) >= '0' && c <= '9');
            if (neg) return -ret;
            return ret;
        }
        
        private byte read() throws IOException {
            if (bufferPointer == bytesRead) fillBuffer();
            return buffer[bufferPointer++];
        }
        
        private void fillBuffer() throws IOException {
            bytesRead = din.read(buffer, 0, BUFFER_SIZE);
            if (bytesRead == -1) buffer[0] = -1;
            bufferPointer = 0;
        }
        
        public void close() throws IOException {
            if (din == null) return;
            din.close();
        }
    }
    
    static class Interval {
        int L, R;
        Interval(int l, int r) {
            this.L = l;
            this.R = r;
        }
    }
    
	public static void main (String[] args) throws java.lang.Exception {
		FastReader in = new FastReader();
		int T = in.nextInt();
		
		// We will reuse arrays up to the maximum possible N across all testcases
		// per the problem constraint sum(N) <= 2*10^5.
		// But for clarity, we'll just allocate anew for each test. That is fine too.
		
		StringBuilder out = new StringBuilder();
		
		while(T-- > 0) {
			int N = in.nextInt();
			int[] H = new int[N];
			for(int i = 0; i < N; i++){
				H[i] = in.nextInt();
			}
			
			// If there is only one peak, there are no pairs of people at all.
			if(N <= 1) {
				out.append("0\n");
				continue;
			}
			
			// 1) Compute L[i]:
			//    L[i] = the smallest index ℓ such that the subarray H[ℓ..i] is distinct.
			int[] L = new int[N];
			int[] lastOcc = new int[N+1];
			Arrays.fill(lastOcc, -1);
			int start = 0;
			for(int i = 0; i < N; i++){
				int h = H[i];
				if(lastOcc[h] >= start){
					start = lastOcc[h] + 1;
				}
				L[i] = start;
				lastOcc[h] = i;
			}
			
			// 2) Compute R[i]:
			//    R[i] = the largest index r such that H[i..r] is distinct.
			int[] R = new int[N];
			int[] nextOcc = new int[N+1];
			Arrays.fill(nextOcc, -1);
			int end = N-1;
			for(int i = N-1; i >= 0; i--){
				if(i > end) {
					end = i;
				}
				int h = H[i];
				int p = nextOcc[h];
				if(p != -1 && p <= end){
					end = p - 1;
				}
				if(end < i){
					end = i;  // ensure valid subarray
				}
				R[i] = end;
				nextOcc[h] = i;
			}
			
			// 3) Build intervals [L[i], R[i]] for i in [0..N-1].
			Interval[] intervals = new Interval[N];
			for(int i = 0; i < N; i++){
				intervals[i] = new Interval(L[i], R[i]);
			}
			
			// 4) Sort intervals by L ascending, then by R ascending
			Arrays.sort(intervals, new Comparator<Interval>() {
				public int compare(Interval a, Interval b) {
					if(a.L != b.L) return Integer.compare(a.L, b.L);
					return Integer.compare(a.R, b.R);
				}
			});
			
			// 5) Count how many pairs of intervals do NOT intersect
			//    We do a standard sweep: for each j, count how many i < j
			//    have intervals[i].R < intervals[j].L.
			long countNonIntersect = 0;
			int p = 0;
			for(int j = 0; j < N; j++){
				int Lj = intervals[j].L;
				while(p < j && intervals[p].R < Lj){
					p++;
				}
				// All intervals from 0..(p-1) do not intersect with j
				countNonIntersect += p;
			}
			
			// Total pairs = N choose 2
			long totalPairs = (long)N * (N - 1) / 2;
			long answer = totalPairs - countNonIntersect;
			
			out.append(answer).append("\n");
		}
		
		System.out.print(out);
	}
}

Explanation of the core idea:

1. For each position i (0-based) in the array H, we determine: – L[i]: how far left we can go without repeating a height.
   Concretely, L[i] is the smallest index ℓ ≤ i such that the subarray H[ℓ..i] is made of distinct heights.
   This can be computed by a standard “last occurrence / sliding window” approach from left to right.

   – R[i]: how far right we can go without repeating a height.
   Concretely, R[i] is the largest index r ≥ i such that the subarray H[i..r] is made of distinct heights.
   This can be computed analogously by scanning from right to left.

   Intuitively, the set of peaks i can ever stand on (possibly via different paths) is exactly all j in the interval [L[i], R[i]].

2. Two people at peaks i and j are “friends” (i.e. can meet) if and only if their intervals [L[i], R[i]] and [L[j], R[j]] intersect.
   Indeed, any common index in the intersection is a peak both can reach.

3. To count the number of intersecting‐interval pairs: – Sort the intervals by their left endpoint L ascending (and R ascending on ties).
   – Sweep through them in this sorted order, and for each interval “j” count how many intervals “i” (with i<j) lie completely to the left (i.e. whose R[i] < L[j]).
   – Those form the non‐intersecting pairs. Summing these yields the count of non‐intersecting pairs.
   – Subtract from the total number of pairs (N*(N-1)/2) to get the count of intersecting (i.e. “friends”) pairs.

This runs in O(N log N) time per test, mainly due to the sort. Since the sum of N across all tests is at most 2×10^5, the overall approach is efficient enough.