Range Sorting (Easy Version) (Codeforces 1827B1)
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):
for _ in range(int(input())):
    n = int(input())
    L = list(map(int, input().split()))
    ans = 0
    X = [0, 0]
    for i in range(1, n):
        Y = [L[i]]
        for j in range(i - 1, -1, -1):
            Y.append(min(Y[-1], L[j]))
        x = i
        nX = [0, 0]
        for kk in range(i - 1, -1, -1):
            if L[kk] > Y[i - x]:
                nX.append(i - kk)
                x = kk
            else:
                nX.append(i - x + X[i - kk] - X[i - x])
        X = nX
        ans += sum(X)
    print(ans)

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
t = int(input())
ans = []
for _ in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    ans0 = 0
    for i in range(n):
        st = []
        for j in range(i, n):
            (aj, ma) = (a[j], a[j])
            while st and st[-1] > aj:
                ma = max(ma, st.pop())
            st.append(ma)
            ans0 += j - i + 1 - len(st)
    ans.append(ans0)
sys.stdout.write('\n'.join(map(str, ans)))

Solution (Python):
import sys
input = sys.stdin.readline
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    ans = 0
    for i in range(n):
        cmp = []
        for j in range(i, n):
            x = a[j]
            sz = 1
            mx = x
            while cmp and x < cmp[-1][0]:
                (r, k) = cmp.pop(-1)
                sz += k
                mx = max(mx, r)
            cmp.append((mx, sz))
            cur = j - i + 1 - len(cmp)
            ans += cur
    print(ans)