Kaosar and Segments (Editorial)

Solution

We are given a permutation of $[1,n]$. Clearly, the maximum element of the permutation is $n$.

Let the position of $n$ in the permutation be $i$ (1-based indexing). Any contiguous subarray (segment) that does not include $n$ will have a maximum strictly less than $n$. Therefore, only the segments fully contained in [1, i-1] (to the left of $n$) and [i+1, n] (to the right of $n$) contribute to the answer.

Recall that the number of non-empty subarrays of length $k$ is \frac{k(k+1)}{2}.

• Number of valid segments to the left of $n$:

  \frac{i(i-1)}{2}

• Number of valid segments to the right of $n$:

  \frac{(n-i)(n-i+1)}{2}

Thus, the total number of segments whose maximum is strictly smaller than the maximum of the permutation is:

Complexity $O(n)$.

for _ in range(int(input())):
    n=int(input())
    p=list(map(int, input().split()))
    m=p.index(n)
    ans=0
    ans+=(m*(m+1))//2
    ans+=((n-m)*(n-m-1))//2
    print(ans)