Shift and Reverse (Codeforces 1907F)
Tags: Greedy, sortings

Given an array of integers $$$a_1, a_2, \ldots, a_n$$$. You can make two types of operations with this array:   Shift: move the last element of array to the first place, and shift all other elements to the right, so you get the array $$$a_n, a_1, a_2, \ldots, a_{n-1}$$$.  Reverse: reverse the whole array, so you get the array $$$a_n, a_{n-1}, \ldots, a_1$$$. Your task is to sort the array in non-decreasing order using the minimal number of operations, or say that it is impossible.

Input: The first line of input contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. Descriptions of test cases follow.The first line of each test case contains an integer $$$n$$$ ($$$1\le n \le 10^5$$$) — size of the array. The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — elements of the array.It is guaranteed that sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output: For each test case output the number $$$k$$$, the minimal number of operations you need to sort the array. If it is impossible to sort the array using these operations, output $$$-1$$$.

Note: In the first test case of the example, to sort the array [$$$3, 2, 1, 5, 4$$$] you need to perform $$$3$$$ operations:  Shift to obtain the array [$$$4, 3, 2, 1, 5$$$];  Shift to obtain the array [$$$5, 4, 3, 2, 1$$$];  Reverse to obtain the array [$$$1, 2, 3, 4, 5$$$]. In the third test case of the example, it can be shown that it is impossible to sort the array using the given operations.In the seventh test case of the example, to sort the array [$$$4, 1, 3, 4, 4$$$] you need to perform $$$3$$$ operations:  Reverse to obtain the array [$$$4, 4, 3, 1, 4$$$];  Shift to obtain the array [$$$4, 4, 4, 3, 1$$$];  Reverse to obtain the array [$$$1, 3, 4, 4, 4$$$]. 

Sample Inputs:
11
5
3 2 1 5 4
5
1 1 2 1 1
4
3 7 10 5
5
1 2 3 4 5
2
5 1
3
3 4 1
5
4 1 3 4 4
3
5 1 1
4
2 5 5 4
5
2 2 1 1 2
2
5 5

Sample Outputs:
3
2
-1
0
1
1
3
1
2
2
0

Solution (Python):
""""""
INF = 10 ** 18

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    b = a[:] + [a[0]]
    cnt_not_sort = 0
    cnt_not_rev = 0
    i_not_sort = -1
    i_not_rev = -1
    for i in range(1, len(b)):
        if b[i] < b[i - 1]:
            cnt_not_sort += 1
            i_not_sort = i
        if b[i] > b[i - 1]:
            cnt_not_rev += 1
            i_not_rev = i
    if min(cnt_not_rev, cnt_not_sort) > 1:
        print(-1)
        return
    ans_sort = INF
    ans_rev = INF
    if cnt_not_sort == 0:
        print(0)
        return
    if cnt_not_rev == 0:
        print(1)
        return
    if cnt_not_sort == 1:
        ans_sort = min(n - i_not_sort, 2 + i_not_sort)
    if cnt_not_rev == 1:
        ans_rev = min(n - i_not_rev, i_not_rev)
        ans_rev += 1
    ans = min(ans_sort, ans_rev)
    if ans == INF:
        print(-1)
        return
    print(ans)

def main():
    t = int(input())
    for _ in range(t):
        solve()
main()

Solution (Python):
inf = int(1000000000.0)

def Tecy():
    n = int(input())
    val = list(map(int, input().split())) * 2
    ans = n
    pre = 0
    count = 0
    flag = False
    for (i, x) in enumerate(val):
        if x >= pre:
            count += 1
            if count == n:
                flag = True
                ans = min(ans, (n * 2 - i - 1) % n)
                ans = min(ans, (i - n + 1) % n + 2)
        else:
            count = 1
        pre = x
    pre = inf
    count = 0
    for (i, x) in enumerate(val):
        if x <= pre:
            count += 1
            if count == n:
                flag = True
                ans = min(ans, (n * 2 - i - 1) % n + 1)
                ans = min(ans, (i - n + 1) % n + 1)
        else:
            count = 1
        pre = x
    if flag:
        print(ans)
    else:
        print(-1)
T = int(input())
for _ in range(T):
    Tecy()

Solution (Python):
import math
for op in range(int(input())):
    n = int(input())
    a = [int(x) for x in input('').split(' ')]
    min_a = min(a)
    ind_min = a.index(min_a)
    n_of_a = a.count(min_a)

    def check_a(a, m):
        ind = 0
        for (i, v) in enumerate(a):
            if v == m:
                continue
            else:
                ind = i
                break
        a1 = a[ind:]
        if len(set(a1)) == 1:
            return [True, 2]
        p = True
        for i in range(1, len(a1)):
            if a1[i] >= a1[i - 1]:
                continue
            else:
                p = False
                break
        if p:
            return [True, 0]
        p = True
        for i in range(1, len(a1)):
            if a1[i] <= a1[i - 1]:
                continue
            else:
                p = False
                break
        if p:
            return [True, 1]
        return [False, -1]
    if ind_min == 0:
        final_min = n
        while final_min > -1:
            if a[final_min - 1] == min_a:
                final_min -= 1
            else:
                break
        new_a = a[final_min:] + a[:final_min]
        (p, t) = check_a(new_a, min_a)
        if final_min == n and p:
            if t == 0 or t == 2:
                res = 0
            if t == 1:
                res = min(n - n_of_a, n_of_a) + 1
        elif final_min != n and p:
            if t == 0:
                res = min(n - final_min, 2 + final_min)
            if t == 1:
                initial_a_count = n_of_a - (n - final_min)
                res = min(1 + initial_a_count, 1 + (n - initial_a_count))
            if t == 2:
                res = min(n - final_min, 1 + n_of_a - (n - final_min))
    else:
        ind1 = int(ind_min)
        for i in range(ind_min, n):
            if a[i] == min_a:
                ind1 = i
            else:
                break
        new_a = a[ind_min:ind1 + 1] + a[ind1 + 1:] + a[:ind_min]
        (p, t) = check_a(new_a, min_a)
        if p:
            if t == 0:
                res = min(n - ind_min, 2 + ind_min)
            if t == 1:
                res = min(1 + ind_min + n_of_a, 1 + (n - ind_min - n_of_a))
            if t == 2:
                res = min(2 + ind_min, 1 + n - ind_min - n_of_a)
    if p:
        print(res)
    else:
        print(-1)