Analysis

We are given $N$ mountain peaks in a line, each with a height $H_i$. Adjacent heights differ by exactly 1, i.e.\ $\lvert H_{i} - H_{i-1}\rvert = 1$. On each peak $i$ there is one person.

A person at peak $i$ can move step‐by‐step to adjacent peaks, but is never allowed to set foot on a height that has been visited before in that path. Equivalently, the path of visited heights must contain no repeats. Because each adjacent step changes the height by $\pm 1$, one can show:

A valid path (with no repeated heights) must be strictly monotonic in index order—i.e.\ it cannot change “direction” (from going up to going down, or vice versa) without immediately revisiting a height.

Hence, from a given peak $i$, that person can only: • move left along a run of strictly increasing or strictly decreasing heights (but not turn around), or
• move right along a run of strictly increasing or strictly decreasing heights (but not turn around), or
• stay put.

Because we only need the possibility of moving along such a path, effectively each index $i$ has two “maximal intervals of reach”: one to the left, one to the right, depending on whether the heights step up or down. Merging those two one‐sided intervals (which overlap at $i$) gives a single “reach interval” $\bigl[L_i, R_i\bigr]\subseteq\{1,\dots,N\}$.

Two people $i$ and $j$ are friends exactly if their reach‐intervals intersect:

$$S(i)\;=\;[\,L_i,\,R_i]\quad\text{and}\quad S(j)\;=\;[\,L_j,\,R_j] \quad\Longrightarrow\quad \text{friends}\;\iff\;S(i)\;\cap\;S(j)\;\neq\;\emptyset.$$

Therefore, the problem reduces to:

1. Compute each person’s interval $[L_i,R_i]$.
2. Count how many pairs $(i,j)$ have intervals that overlap.

Step 2 is a classical “count the number of intersecting‐interval pairs” problem, which can be done in $O(N\log N)$ via a standard sweep‐line or two‐pointer approach.

Because the sum of all $N$ over all testcases is at most $2\times10^5$, an $O(N\log N)$ solution per test is acceptable overall.

---

Outline of the Solution

1. Read input. For each test:

   • Read $N$, read the heights array $H$.

2. Edge case: If $N=1$, there are no pairs, so answer is 0 immediately.

3. Build the “direction” array $D$ of length $N-1$, where

   $$D[i] \;=\; \begin{cases} +1 & \text{if }\,H[i+1]>H[i],\\ -1 & \text{if }\,H[i+1]<H[i]. \end{cases}$$

   (All differences are $\pm 1$.)

4. Precompute “maximal run” boundaries going left and right:

   • We will keep two arrays, upLeft[] and downLeft[], which say:
     “If the step from $(i-1)\to i$ is +1, then upLeft[i] is how far left we can extend maintaining +1 steps.
     If that step is -1, then downLeft[i] is how far left we can extend with -1 steps.”
     We do this in a single pass from left to right.
   • Likewise define upRight[] and downRight[] by going right‐to‐left.

   Concretely (1-based indexing):

   • Initialize: upLeft[1] = 1, downLeft[1] = 1
     upRight[N] = N, downRight[N] = N
   • Left to right: for i in 2..N: if D[i-1] == +1 then upLeft[i] = upLeft[i-1] else upLeft[i] = i if D[i-1] == -1 then downLeft[i] = downLeft[i-1] else downLeft[i] = i
   • Right to left: for i in (N-1) down to 1: if D[i] == +1 then upRight[i] = upRight[i+1] else upRight[i] = i if D[i] == -1 then downRight[i] = downRight[i+1] else downRight[i] = i

5. Assign each index $i$ a single interval $[\,L_i,\,R_i]$ which is the (union of) the left and right runs, but they always overlap at $i$, so it becomes a single continuous interval:

   • If $i=1$, then $L_1 = 1$.
     Otherwise, look at the sign $D[i-1]$; if $D[i-1]=+1$ use $L_i = \text{upLeft}[i]$, else $L_i = \text{downLeft}[i]$.
   • If $i=N$, then $R_N = N$.
     Otherwise, if $D[i]=+1$ then $R_i = \text{upRight}[i]$, else $R_i = \text{downRight}[i]$.

   So the person at peak $i$ can reach exactly the integer indices in $\bigl[L_i,\,R_i\bigr]$.

6. Count intersecting‐interval pairs. Each person $i$ has interval $(\mathit{start}_i,\mathit{end}_i)$. We want how many $(i,j)$ have

   $$\bigl[\mathit{start}_i,\;\mathit{end}_i\bigr] \;\cap\; \bigl[\mathit{start}_j,\;\mathit{end}_j\bigr] \;\neq\;\emptyset.$$

   A standard sweep‐line in ascending order of “start” works:

   • Sort all intervals by their start coordinate (if tie, by end).
   • Maintain a min‐heap (or balanced structure) of the “end” values of all intervals that have started but not yet “fully ended”.
   • For each interval in increasing order of start = s:
     • While the heap’s smallest end < s, pop it (it cannot intersect s or anything starting ≥ s).
     • The remaining heap size = number of intervals that do intersect the current one. Add that to the running total.
     • Push this current interval’s end into the heap.
   • The accumulated total is the number of intersecting pairs.

That total is our answer for the test.

---

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

class Codechef
{
    static FastInput in = new FastInput(System.in);
    static PrintWriter out = new PrintWriter(System.out,false);

    public static void main(String[] args)
    {
        int T = in.nextInt();
        while (T-- > 0) {
            int N = in.nextInt();
            int[] H = new int[N];
            for(int i=0; i<N; i++){
                H[i] = in.nextInt();
            }
            
            // Edge case: N=1 => no pairs
            if(N<=1){
                out.println(0);
                continue;
            }
            
            // Build D array: D[i] = +1 if H[i+1]>H[i], -1 otherwise
            // 1-based logic means D[i] = sign(H[i+1]-H[i]) for i=1..(N-1), but let's keep 0-based in code
            int[] D = new int[N-1];
            for(int i=0; i<N-1; i++){
                D[i] = (H[i+1] > H[i])? +1 : -1;
            }
            
            // upLeft[i], downLeft[i] (1-based concept, but we'll do 0-based in code):
            int[] upLeft   = new int[N];
            int[] downLeft = new int[N];
            
            upLeft[0] = 0;
            downLeft[0] = 0;
            for(int i=1; i<N; i++){
                if(D[i-1]== +1){
                    // continue up run
                    upLeft[i] = upLeft[i-1];
                } else {
                    upLeft[i] = i;
                }
                if(D[i-1]== -1){
                    // continue down run
                    downLeft[i] = downLeft[i-1];
                } else {
                    downLeft[i] = i;
                }
            }
            
            // upRight[i], downRight[i]
            int[] upRight   = new int[N];
            int[] downRight = new int[N];
            upRight[N-1]   = N-1;
            downRight[N-1] = N-1;
            for(int i=N-2; i>=0; i--){
                if(D[i]== +1){
                    upRight[i] = upRight[i+1];
                } else {
                    upRight[i] = i;
                }
                if(D[i]== -1){
                    downRight[i] = downRight[i+1];
                } else {
                    downRight[i] = i;
                }
            }
            
            // Build intervals [L[i], R[i]] for each i in 0..N-1
            // Converting the 1-based formula to 0-based carefully:
            //   L[i] = if i==0 => 0
            //           else if D[i-1]==+1 => upLeft[i]
            //                else => downLeft[i]
            //   R[i] = if i==N-1 => N-1
            //           else if D[i]==+1 => upRight[i]
            //                else => downRight[i]
            // and each person's final interval is inclusive, over indices 0..N-1.
            
            long[][] intervals = new long[N][2]; // each row: [start, end]
            
            for(int i=0; i<N; i++){
                // Compute L[i]
                int L;
                if(i==0){
                    L = 0;
                } else {
                    if(D[i-1]== +1){
                        L = upLeft[i];
                    } else {
                        L = downLeft[i];
                    }
                }
                // Compute R[i]
                int R;
                if(i==N-1){
                    R = N-1;
                } else {
                    if(D[i]== +1){
                        R = upRight[i];
                    } else {
                        R = downRight[i];
                    }
                }
                intervals[i][0] = L;     // start
                intervals[i][1] = R;     // end
            }
            
            // Now count how many pairs (i,j) have intervals overlapping
            // We'll do a standard sweep by "start"
            Arrays.sort(intervals, (a,b) -> {
                if(a[0]<b[0]) return -1; else if(a[0]>b[0]) return +1;
                // tie => compare end
                if(a[1]<b[1]) return -1; else if(a[1]>b[1]) return +1;
                return 0;
            });
            
            // Sweep line: for each interval in ascending start,
            // pop from a min-heap all intervals whose end < current.start,
            // then add the current interval's end to the heap
            // number of intervals left in the heap is how many we intersect with
            PriorityQueue<Long> minHeap = new PriorityQueue<>();
            long count = 0L;
            
            for(int i=0; i<N; i++){
                long start = intervals[i][0];
                long end   = intervals[i][1];
                // pop all intervals that ended before 'start'
                while(!minHeap.isEmpty() && minHeap.peek()<start){
                    minHeap.poll();
                }
                // all intervals left are those that end >= start => they intersect
                count += minHeap.size();
                // now add this interval's end
                minHeap.offer(end);
            }
            
            out.println(count);
        }
        
        out.flush();
    }
    
    // A simple fast input helper (not strictly required, but often helpful in large IO):
    static class FastInput {
        private final BufferedInputStream buf;
        private int bId = 0, size = 0;
        private byte[] buffer = new byte[1<<16];
        
        FastInput(InputStream in) {
            buf = new BufferedInputStream(in);
        }
        private byte read() {
            if(bId==size){
                try {
                    size = buf.read(buffer);
                } catch(IOException e){ throw new RuntimeException(e); }
                if(size==-1) return -1;
                bId=0;
            }
            return buffer[bId++];
        }
        private boolean isSpace(byte c){return c==' '||c=='\n'||c=='\r'||c=='\t'||c==-1;}
        int nextInt() {
            int sign=1;
            byte c=read();
            while(isSpace(c)) c=read();
            if(c=='-'){ sign=-1; c=read(); }
            int val=0;
            while(!isSpace(c)){
                if(c<'0'||c>'9') throw new RuntimeException("Unexpected character "+(char)c);
                val=val*10+(c-'0');
                c=read();
            }
            return val*sign;
        }
    }
}

Explanation of the key steps:

• We transform the “cannot revisit heights” rule into “any valid walk must be strictly monotonic in index order.”
• From each index i, we figure out how far left we can go (without changing +1/−1 direction) and how far right likewise. Merging them gives one continuous interval [Lᵢ, Rᵢ].
• Two indices i, j can meet if and only if [Lᵢ, Rᵢ] intersects [Lⱼ, Rⱼ].
• We then do a standard counting of intersecting intervals via sorting and a min‐heap.

This solves the problem in O(N log N) time per test, which is efficient for the given constraints.