Analysis

We have an array of mountain‐heights H[1..N] with the property that adjacent heights differ by exactly 1. On each peak i there is one person of height H[i]. A person may walk step‐by‐step left or right, but is not allowed to visit any height-value that (s)he has visited before. Two people are said to be “friends” if there is some mountain k that they can both reach (possibly by different routes), under the no‐repeated‐heights constraint.

A key (perhaps surprising) simplification is:

A sub‐path in this array has no repeated height if and only if it is a “strictly‐monotonic” subsequence of the heights.

Why?
Because the height‐array has the property
│H[i+1] − H[i]│ = 1.
If a path ever “turns around” in height (i.e., goes up then later goes down, or vice versa), that guarantees re‐visiting a previously‐seen height in a ±1 walk. Conversely, if the sub‐path is purely up or purely down in height, then no height is repeated.

From that fact one can show:

1. For any two indices i < j, the subarray H[i..j] is entirely valid (no repeated heights) if and only if H[i..j] is strictly‐increasing or strictly‐decreasing in index‐order.
2. More generally, if a single run of ±1‐differences covers i..j (with no sign‐change in the differences), then i can “walk” to j within that subarray.

Hence the array of “differences”
D[k] = H[k+1] − H[k] (each D[k] is either +1 or −1)
can be broken into maximal runs of consecutive + or −. For example, if
D = [+,+,−,−,+,+,−,…]
then one finds contiguous blocks where D is all +, then (possibly) a block where D is all −, etc. Each such block of D from indices a..b corresponds to a strictly‐monotonic subarray of H covering the mountain‐indices [a..(b+1)]. Call each such block a “run.”

• Inside a single run r, all indices in that run can reach one another (so all those people are mutual friends).
• If two runs r and r+1 are adjacent, they share exactly one boundary‐index in H (namely b₍r₎+1 = a₍r+1₎). A person i in run r (but not also in r+1) and a person j in run r+1 (but not also in r) can nevertheless meet at that shared boundary‐peak.

Putting it more concretely:

• Let the difference‐array D of length (N−1) be
S[i] = sign(D[i]) ∈ {+1, −1}.

• Scan S from left to right to find its maximal constant‐sign runs. Suppose we end up with M runs, each run r given by an interval (aᵣ..bᵣ) in the difference‐array indices. In terms of mountain‐indices 1..N, run r covers the subarray [aᵣ..bᵣ + 1] of the H‐array (inclusive).

• The “size” of run r is
size(r) = (bᵣ − aᵣ + 1) + 1 = bᵣ − aᵣ + 2
because a run of length L in the difference‐array covers L+1 points in H.

Once we have these runs:

1. All pairs within the same run.
   Inside run r of size(r) points, every pair of distinct indices is a valid friendship. That contributes
   C( size(r), 2 )
   to the friendship count.

2. All cross‐run pairs that meet at a shared boundary.
   Consecutive runs r and r+1 share exactly one boundary index bᵣ+1 = aᵣ₊_1. Any i strictly inside run r (so i≠boundary) and j strictly inside run r+1 can meet at that boundary. The number of i in run r but not also in run r+1 is size(r)−1 (we remove the boundary index), and similarly run r+1 has size(r+1)−1 points not also in run r. Hence the cross‐product
   (size(r)−1) × (size(r+1)−1)
   counts how many new i–j pairs are formed by people i in run r exclusively and j in run r+1 exclusively.

Summing these two contributions gives the total count of “friends.”

Formally:

• Let runs = (a_1..b_1), (a_2..b_2), …, (aₘ..bₘ) be the runs in D, from left to right.
• For r = 1..m, define
size(r) = (bᵣ − aᵣ + 2).
• Then the answer =
Σᵣ C( size(r), 2 )

• Σᵣ₌_1…(m−1) [ (size(r) − 1) × (size(r+1) − 1 ) ].

That formula can be implemented in O(N) time (per test) by first scanning S to find its runs, and then doing a single pass over those runs.

Below is a reference‐implementation in Python.

python
def solve():
    import sys
    input_data = sys.stdin.read().strip().split()
    t = int(input_data[0])
    idx_data = 1
    
    answers = []
    for _testcase in range(t):
        N = int(input_data[idx_data]); idx_data += 1
        H = input_data[idx_data: idx_data + N]
        idx_data += N
        H = list(map(int, H))
        
        # If there is only 1 person, no pairs.
        if N <= 1:
            answers.append(0)
            continue
        
        # Build the "sign array" S = sign(H[i+1] - H[i]) for i=1..N-1
        # Each S[i] is either +1 or -1 (we can store it as True/False or just +1/-1).
        S = []
        for i in range(N-1):
            if H[i+1] > H[i]:
                S.append(1)
            else:
                S.append(-1)
        
        # Find maximal runs of consecutive equal signs in S.
        runs = []
        start = 0  # will store runs by zero-based indices for S
        for i in range(len(S) - 1):
            if S[i] != S[i+1]:
                # we close the run from 'start'..'i'
                runs.append((start, i))
                start = i + 1
        # close final run
        runs.append((start, len(S) - 1))
        
        # Now each run (a, b) in S corresponds to [a..b+1] in mountain indices.
        # size = (b - a + 1) + 1 = b - a + 2.
        sizes = []
        for (a, b) in runs:
            size_run = (b - a + 2)
            sizes.append(size_run)
        
        # Sum up intra-run friendships:
        # sum_{r}  C(sizes[r], 2) = sum_{r} sizes[r]*(sizes[r]-1)/2
        # (use integer arithmetic carefully)
        total = 0
        for sz in sizes:
            total += sz*(sz-1)//2
        
        # Add cross-run pairs:
        # For consecutive runs r, r+1, the boundary is shared;
        # each run's "interior" has size(r)-1
        for i in range(len(sizes) - 1):
            total += (sizes[i] - 1)*(sizes[i+1] - 1)
        
        answers.append(total)
    
    # Print all answers
    print('\n'.join(map(str, answers)))

Explanation of key steps:

1. Read T testcases.
2. For each test, read N and then the array H of length N.
3. If N = 1, answer is 0 (no pairs).
4. Otherwise, build the sign‐array S of length N−1, with each entry being +1 or −1 depending on whether H[i+1] > H[i] or < H[i].
5. Partition S into maximal runs of consecutive equal signs. Each run r goes from index aᵣ..bᵣ in S.
   – This run corresponds to a strictly‐monotonic subarray of the mountains covering H‐indices [aᵣ..bᵣ+1].
   – Its “size” is bᵣ−aᵣ+2 (the number of mountain‐indices in that run).
6. Sum up all intra‐run pairs via ∑ C(size(r),2).
7. For each pair of consecutive runs, add (size(r)−1)*(size(r+1)−1). These come from i in run r exclusively and j in run r+1 exclusively, who can still meet at the shared boundary peak.
8. Output the final sum.

This solves the problem in O(N) time per test (where N is the number of peaks in that test) and correctly handles all edge‐cases.