Analysis

We have an array of heights H[1..N] with the property that adjacent heights differ by exactly 1, and a person starting on peak i can "walk" left or right along the chain but may never revisit a height that has been visited before on that walk. Two people (at positions i and j) are said to be friends if there is some peak k they can both reach (possibly via different walks).

A key (and somewhat tricky) insight is:

i and j are friends ⟺ there is some index k such that
• the contiguous subarray of indices [min(i,k) .. max(i,k)] has no repeated height (so i can reach k), and
• the contiguous subarray [min(j,k) .. max(j,k)] has no repeated height (so j can reach k).

Equivalently, one can show that:

1. If the contiguous subarray [i..j] is itself free of repeated heights, then clearly i can just walk directly to j (and j stays put), so i and j meet at j.
2. Even if [i..j] does contain repeats, i and j can still meet at some intermediate k (with i < k < j, or k < i < j, etc.) provided the two "sub‐paths" [i..k], [j..k] themselves have no repeated heights.

It turns out one can count the number of friendly pairs by splitting into two main cases:

• Case B ("meet at or beyond j"):
If [i..j] has no repeated heights, then j ≤ bᵢ, where bᵢ is the largest index ≥ i such that [i..bᵢ] is distinct.
In other words, for each i, all j in the range (i..bᵢ] yield a friend‐pair (i,j).

• Case A ("meet strictly in the interior"):
If [i..j] does have repeats, it may still be possible to meet at some k with i < k < j.
One finds that the condition boils down to
cⱼ ≤ bᵢ < j
(plus i < j),
where cⱼ is the smallest index ≤ j for which [cⱼ..j] is distinct.
Intuitively, this means i's “forward‐distinct window” ends at bᵢ, which is still to the left of j (so [i..j] is not distinct).
But j can “go backward” at least one step (since cⱼ < j), and if cⱼ ≤ bᵢ, they can meet in between.

Hence, the counting strategy:

1. Compute for each i the value bᵢ = the furthest index ≥ i such that [i..bᵢ] is distinct.

2. Compute for each i the value cᵢ = the furthest index ≤ i such that [cᵢ..i] is distinct.

3. Let
   • sumB = ∑(bᵢ−i) over all i, counting all pairs (i,j) with i < j ≤ bᵢ.
   • Then count how many additional pairs arise under the interior‐meeting scenario, i.e. pairs (i,j) with
   i < j, bᵢ < j, and bᵢ ≥ cⱼ.

   One can count these in O(N log N) total (over all testcases) by a Fenwick (BIT) or Segment‐Tree approach:

   • We iterate j from 1..N in ascending order.
   • Keep indices i < j in a Fenwick tree keyed by bᵢ.
   • Each time we move j forward, we "insert" into the Fenwick all i that have just become < j.
   • Then we query how many such i satisfy bᵢ ∈ [cⱼ.. (j−1)].
   • This yields how many new friendly pairs (i,j) come from the interior‐meeting condition.

Finally, total_friends = sumB + sumA′, where sumA′ is the Fenwick‐accumulated count of (i,j) that meet in the interior.

This algorithm runs in O(N log N) per test (where N is the size of that test). Since the sum of N over all T testcases is at most 2×10^5, the total run‐time is about O(N log N) ≈ 2×10^5 × log(2×10^5) which is acceptable.

Below is a complete Java implementation.

────────────────────────────────────────────────────────

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

class Codechef
{
    // Fenwick (BIT) for counting how many b[i] lie in a given range
    static class Fenwick {
        int n;
        long[] fenw;
        
        Fenwick(int n) {
            this.n = n;
            fenw = new long[n+1];
        }
        
        // add "val" at index idx
        void update(int idx, long val) {
            for (; idx <= n; idx += idx & -idx) {
                fenw[idx] += val;
            }
        }
        
        // sum from 1..idx
        long query(int idx) {
            long s = 0;
            for (; idx > 0; idx -= idx & -idx) {
                s += fenw[idx];
            }
            return s;
        }
        
        // sum in [l..r]
        long rangeQuery(int l, int r) {
            if (r < l) return 0;
            return query(r) - query(l-1);
        }
    }
    
	public static void main (String[] args) throws java.lang.Exception
	{
		FastReader in = new FastReader();
		PrintWriter out = new PrintWriter(System.out,false);
		
		int T = in.nextInt();
		while(T-- > 0) {
		    int N = in.nextInt();
		    int[] H = new int[N+1];
		    for(int i=1; i<=N; i++){
		        H[i] = in.nextInt();
		    }
		    
		    // 1) Compute b[i] = rightMax[i]:
		    //    largest index r >= i s.t. H[i..r] is distinct.
		    int[] b = new int[N+1];
		    Arrays.fill(b, 0);
		    // We'll do a right-to-left pass with a "lastOcc" & a pointer "end".
		    int[] lastOccB = new int[N+1];    // heights up to N
		    Arrays.fill(lastOccB, N+1);       // "not seen yet"
		    int end = N;
		    for(int i=N; i>=1; i--) {
		        if(lastOccB[H[i]] <= end) {
		            end = Math.min(end, lastOccB[H[i]] - 1);
		        }
		        b[i] = end;
		        lastOccB[H[i]] = i;
		    }
		    
		    // 2) Compute c[i] = leftMax[i]:
		    //    smallest index L <= i s.t. H[L..i] is distinct.
		    int[] c = new int[N+1];
		    Arrays.fill(c, 0);
		    int[] lastOccC = new int[N+1];  // for left pass
		    Arrays.fill(lastOccC, -1);
		    int start = 1;
		    for(int i=1; i<=N; i++){
		        if(lastOccC[H[i]] >= start){
		            start = lastOccC[H[i]] + 1;
		        }
		        c[i] = start;
		        lastOccC[H[i]] = i;
		    }
		    
		    // 3) sumB = sum over i of (b[i] - i) for b[i] >= i
		    long sumB = 0;
		    for(int i=1; i<=N; i++){
		        if(b[i] >= i) {
		            sumB += (b[i] - i);
		        }
		    }
		    
		    // 4) count pairs that meet in the interior ("A'")
		    //    We want those (i,j) with i<j, b[i] < j, and b[i] >= c[j].
		    //    We'll use Fenwicks for b[i].
		    Fenwick fenw = new Fenwick(N);
		    
		    long sumA = 0;
		    int ptr = 1;  
		    // We'll iterate j from 1..N
		    for(int j=1; j<=N; j++){
		        // Add all i < j into Fenwicks (if b[i] > i, meaning i can move at least 1 forward)
		        while(ptr < j) {
		            if(b[ptr] > ptr) {
		                int pos = b[ptr]; 
		                // clamp to [1..N] anyway
		                if(pos < 1) pos = 1;
		                if(pos > N) pos = N;
		                fenw.update(pos, 1L);
		            }
		            ptr++;
		        }
		        // Now query how many i have c[j] <= b[i] < j
		        // i.e. b[i] in [c[j], j-1], if c[j] <= j-1
		        int leftBound = c[j];
		        int rightBound = j-1;
		        if(leftBound <= rightBound) {
		            sumA += fenw.rangeQuery(leftBound, rightBound);
		        }
		    }
		    
		    long ans = sumB + sumA;
		    out.println(ans);
		}
		
		out.flush();
	}
	
    // a fast input reader, typical for large input
	static class FastReader
	{
		BufferedReader br;
		StringTokenizer st;
		public FastReader()
		{
			br = new BufferedReader(new InputStreamReader(System.in));
		}

		String next()
		{
			while (st == null || !st.hasMoreElements())
			{
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException  e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}

		int nextInt() { return Integer.parseInt(next()); }
		long nextLong() { return Long.parseLong(next()); }
		double nextDouble() { return Double.parseDouble(next()); }
		String nextLine()
		{
			String str = "";
			try {
				str = br.readLine();
			} catch (IOException e) {
				e.printStackTrace();
			}
			return str;
		}
	}
}

Explanation of key parts:

1. We compute array b[] (“rightMax”):

   • b[i] is the largest r ≥ i so that the subarray H[i..r] is distinct.
   • Done by traversing from right to left; when we see a repeat lastOccB[ H[i] ] that is ≤ our current “end”, we shrink “end”.

2. We compute array c[] (“leftMax”):

   • c[i] is the smallest L ≤ i so that H[L..i] is distinct.
   • Done by a standard left‐to‐right sliding‐window approach.

3. The sum ∑(b[i]−i) counts all pairs (i,j) with i<j ≤ b[i], i.e. those pairs that can “meet to the right” at j (or beyond).

4. For the “meet in the interior” situation, we collect all i in a Fenwick tree keyed by b[i], then for each j we query how many i < j have c[j] ≤ b[i] < j.

   Physically this says:
   – “b[i] < j” ensures [i..j] is not distinct.
   – but “b[i] ≥ c[j]” means j can step backward at least one step (c[j] < j), and i’s forward‐distinct range and j’s backward‐distinct range do overlap, allowing an interior k.

Summing these two counts gives the total number of friendly pairs.