Range Sorting (Easy Version) (Codeforces 1828D1)
Tags: Greedy, dsu

The only difference between this problem and the hard version is the constraints on $$$t$$$ and $$$n$$$.You are given an array $$$a$$$, consisting of $$$n$$$ distinct integers $$$a_1, a_2, \ldots, a_n$$$. Define the beauty of an array $$$p_1, p_2, \ldots p_k$$$ as the minimum amount of time needed to sort this array using an arbitrary number of range-sort operations. In each range-sort operation, you will do the following:   Choose two integers $$$l$$$ and $$$r$$$ ($$$1 \le l < r \le k$$$).  Sort the subarray $$$p_l, p_{l + 1}, \ldots, p_r$$$ in $$$r - l$$$ seconds. Please calculate the sum of beauty over all subarrays of array $$$a$$$.A subarray of an array is defined as a sequence of consecutive elements of the array.

Input: Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 5 \cdot 10^3$$$). The description of the test cases follows.The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 5 \cdot 10^3$$$) — the length of the array $$$a$$$.The second line of each test case consists of $$$n$$$ integers $$$a_1,a_2,\ldots, a_n$$$ ($$$1\le a_i\le 10^9$$$). It is guaranteed that all elements of $$$a$$$ are pairwise distinct.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5 \cdot 10^3$$$.

Output: For each test case, output the sum of beauty over all subarrays of array $$$a$$$.

Note: In the first test case:   The subarray $$$[6]$$$ is already sorted, so its beauty is $$$0$$$.  The subarray $$$[4]$$$ is already sorted, so its beauty is $$$0$$$.  You can sort the subarray $$$[6, 4]$$$ in one operation by choosing $$$l = 1$$$ and $$$r = 2$$$. Its beauty is equal to $$$1$$$.  The sum of beauty over all subarrays of the given array is equal to $$$0 + 0 + 1 = 1$$$.In the second test case:   The subarray $$$[3]$$$ is already sorted, so its beauty is $$$0$$$.  The subarray $$$[10]$$$ is already sorted, so its beauty is $$$0$$$.  The subarray $$$[6]$$$ is already sorted, so its beauty is $$$0$$$.  The subarray $$$[3, 10]$$$ is already sorted, so its beauty is $$$0$$$.  You can sort the subarray $$$[10, 6]$$$ in one operation by choosing $$$l = 1$$$ and $$$r = 2$$$. Its beauty is equal to $$$2 - 1 = 1$$$.  You can sort the subarray $$$[3, 10, 6]$$$ in one operation by choosing $$$l = 2$$$ and $$$r = 3$$$. Its beauty is equal to $$$3 - 2 = 1$$$.  The sum of beauty over all subarrays of the given array is equal to $$$0 + 0 + 0 + 0 + 1 + 1 = 2$$$.

Sample Inputs:
5
2
6 4
3
3 10 6
4
4 8 7 2
5
9 8 2 4 6
12
2 6 13 3 15 5 10 8 16 9 11 18

Sample Outputs:
1
2
8
16
232

Solution (Python):
inf = 10 ** 7
for _ in range(int(input())):
    N = int(input())
    A = list(map(int, input().split()))
    ans = 0
    for i in range(N):
        ans += i * (N - i)
    for i in range(N):
        M = inf
        for j in range(i - 1, -1, -1):
            if A[j] < A[i]:
                M = j
                break
        if M == inf:
            continue
        x = -1
        y = N
        for j in range(M - 1, -1, -1):
            if A[j] > A[i]:
                x = j
                break
        for j in range(i + 1, N):
            if A[j] < A[i]:
                y = j
                break
        ans -= (M - x) * (y - i)
    print(ans)

Solution (Python):
def max_beauty(n):
    ans = 0
    for i in range(n + 1):
        ans += i * (n - i)
    return ans

def divide(a, i):
    (l, r) = (i, i + 1)
    if a[l] > a[r]:
        return 0
    r_mins = [[a[r], r]]
    while r + 1 < len(a) and a[r + 1] > a[i]:
        r += 1
        if a[r] < r_mins[-1][0]:
            r_mins.append([a[r], r])
        else:
            r_mins[-1][1] = r
    l_maxs = [[a[l], l]]
    while l - 1 >= 0 and a[l - 1] < a[i + 1]:
        l -= 1
        if a[l] > l_maxs[-1][0]:
            l_maxs.append([a[l], l])
        else:
            l_maxs[-1][1] = l
    subs = 0
    (li, ri) = (0, len(r_mins) - 1)
    last_l = i + 1
    while li < len(l_maxs) and ri >= 0:
        while li + 1 < len(l_maxs) and l_maxs[li + 1][0] < r_mins[ri][0]:
            li += 1
        subs += (last_l - l_maxs[li][1]) * (r_mins[ri][1] - i)
        last_l = l_maxs[li][1]
        li += 1
        while li < len(l_maxs) and ri >= -1 and (l_maxs[li][0] > r_mins[ri][0]):
            ri -= 1
    return subs

def beauty(a):
    ans = max_beauty(len(a))
    for i in range(len(a) - 1):
        ans -= divide(a, i)
    return ans
t = int(input())
for _ in range(t):
    n = int(input())
    a = input().strip().split(' ')
    a = [int(i) for i in a]
    print(beauty(a))

Solution (Python):
import sys
import math
rd = sys.stdin.readline
t = int(rd())
for _ in range(t):
    n = int(rd())
    arr = list(map(int, rd().split()))
    ans = 0
    for i in range(n):
        a = [arr[i]]
        for j in range(i + 1, n):
            if arr[j] > a[-1]:
                a.append(arr[j])
            else:
                m = a.pop()
                while len(a) > 0 and a[-1] > arr[j]:
                    a.pop()
                a.append(m)
            ans += j - i + 1 - len(a)
    print(ans)