Sort the Subarray (Codeforces 1821B)
Tags: Greedy, brute force

Monocarp had an array $$$a$$$ consisting of $$$n$$$ integers. He has decided to choose two integers $$$l$$$ and $$$r$$$ such that $$$1 \le l \le r \le n$$$, and then sort the subarray $$$a[l..r]$$$ (the subarray $$$a[l..r]$$$ is the part of the array $$$a$$$ containing the elements $$$a_l, a_{l+1}, a_{l+2}, \dots, a_{r-1}, a_r$$$) in non-descending order. After sorting the subarray, Monocarp has obtained a new array, which we denote as $$$a'$$$.For example, if $$$a = [6, 7, 3, 4, 4, 6, 5]$$$, and Monocarp has chosen $$$l = 2, r = 5$$$, then $$$a' = [6, 3, 4, 4, 7, 6, 5]$$$.You are given the arrays $$$a$$$ and $$$a'$$$. Find the integers $$$l$$$ and $$$r$$$ that Monocarp could have chosen. If there are multiple pairs of values $$$(l, r)$$$, find the one which corresponds to the longest subarray.

Input: The first line contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.Each test case consists of three lines:  the first line contains one integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$);  the second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$);  the third line contains $$$n$$$ integers $$$a'_1, a'_2, \dots, a'_n$$$ ($$$1 \le a'_i \le n$$$). Additional constraints on the input:  the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$;  it is possible to obtain the array $$$a'$$$ by sorting one subarray of $$$a$$$;  $$$a' \ne a$$$ (there exists at least one position in which these two arrays are different). 

Output: For each test case, print two integers — the values of $$$l$$$ and $$$r$$$ ($$$1 \le l \le r \le n$$$). If there are multiple answers, print the values that correspond to the longest subarray. If there are still multiple answers, print any of them.


Sample Inputs:
3
7
6 7 3 4 4 6 5
6 3 4 4 7 6 5
3
1 2 1
1 1 2
3
2 2 1
2 1 2

Sample Outputs:
2 5
1 3
2 3

Solution (Python):
import io, os
from sys import stdout
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
t = int(input())
while t:
    n = int(input())
    a = list(map(int, input().split()))
    a1 = list(map(int, input().split()))
    (l, r) = (-1, -1)
    for i in range(n):
        if a[i] != a1[i]:
            l = i
            break
    for i in range(n - 1, -1, -1):
        if a[i] != a1[i]:
            r = i
            break
    ma = a1[r]
    mi = a1[l]
    ''
    for i in range(l - 1, -1, -1):
        if a[i] <= mi:
            mi = a[i]
            l = i
        else:
            break
    for i in range(r + 1, n):
        if a[i] >= ma:
            ma = a[i]
            r = i
        else:
            break
    stdout.write(f'{l + 1} {r + 1}\n')
    t -= 1

Solution (Python):
import sys
input = sys.stdin.readline
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    (l, r) = (-1, -1)
    for i in range(n):
        if a[i] != b[i]:
            r = i
            if l == -1:
                l = i
    while l > 0 and b[l - 1] <= b[l]:
        l -= 1
    while r < n - 1 and b[r] <= b[r + 1]:
        r += 1
    print(l + 1, end=' ')
    print(r + 1)

Solution (Python):
import sys
input = sys.stdin.readline

class Solver:

    def solve(self, a, a_dash):
        l = 0
        while l < len(a) and a[l] == a_dash[l]:
            l += 1
        r = len(a) - 1
        while r > l and a[r] == a_dash[r]:
            r -= 1
        l = min(l, len(a) - 1)
        while l > 0 and a_dash[l] >= a_dash[l - 1]:
            l -= 1
        while r < len(a) - 1 and a_dash[r] <= a_dash[r + 1]:
            r += 1
        print(max(l, 0) + 1, min(r, len(a)) + 1)
if __name__ == '__main__':
    solver = Solver()
    t = int(input())
    for i in range(t):
        n = int(input())
        a = list(map(int, input().split()))
        a_dash = list(map(int, input().split()))
        solver.solve(a, a_dash)