Problem:
Bozosort Bozosort, as well as Bogosort, is a very inefficient sort algorithm. It is a random number-based algorithm that sorts sequence elements following the steps as below:  Randomly select two elements and swap them.  Verify if all the elements are sorted in increasing order.  Finish if sorted, else return to 1.  To analyze Bozosort, you have decided to simulate the process using several predetermined pairs of elements. You are given several commands to swap two elements. Make a program to evaluate how many times you have to run the command before the sequence is aligned in increasing order. Input The input is given in the following format. $N$
$a_1$ $a_2$ ... $a_N$
$Q$
$x_1$ $y_1$
$x_2$ $y_2$
$...$
$x_Q$ $y_Q$ The first line provides the number of sequence elements $N$ ($2 \leq N \leq 300,000$). The second line provides an array of integers $a_i$ ($1 \leq a_i \leq 10^9$) that constitutes the sequence. Each of the subsequent $Q$ lines provides a pair of integers $x_i,y_i$ ($1 \leq x_i,y_i \leq N$) that represent the $i$-th command, which swaps the two elements indicated by $x_i$ and $y_i$ ($x_i \ne y_i$). Output If neat alignment in increasing order is realized the first time after execution of multiple commands, output at what time it was. Output 0 if the initial sequence is aligned in increasing order, and -1 if exhaustive execution still failed to attain the goal. Sample Input 1 6
9 7 5 6 3 1
3
1 6
2 5
3 4 Sample Output 1 2 Sample Input 2 4
4 3 2 1
2
1 2
3 4 Sample Output 2 -1 Sample Input 3 5
1 1 1 2 2
1
1 2 Sample Input 3 0

Solution (Python):

def solve():
    N = int(input())
    a = [int(i) for i in input().split()]
    Q = int(input())
    sort_a = sorted(a)
    judge = 0
    for i in range(N):
        if a[i] != sort_a[i]:
            judge += 1
    if judge == 0:
        print(0)
    else:
        for i in range(Q):
            x, y = map(int, input().split())
            tmp = a[x - 1]
            a[x - 1] = a[y - 1]
            a[y - 1] = tmp
            if a[x - 1] == sort_a[x - 1] and a[y - 1] != sort_a[x - 1]:
                judge -= 1
            if a[x - 1] != sort_a[x - 1] and a[y - 1] == sort_a[x - 1]:
                judge += 1
            if a[y - 1] == sort_a[y - 1] and a[x - 1] != sort_a[y - 1]:
                judge -= 1
            if a[y - 1] != sort_a[y - 1] and a[x - 1] == sort_a[y - 1]:
                judge += 1
            if judge == 0:
                print(i + 1)
                break
        else:
            print(-1)


if __name__ == '__main__':
    solve()

Solution (Python):
import sys
readline = sys.stdin.readline
N = int(readline())
*A, = map(int, readline().split())
C = A[:]
C.sort()

MOD = 4253024257
base = 3
B = [0]*N
v = 1
P = Q = 0
for i in range(N):
    B[i] = v
    P += v * A[i]
    Q += v * C[i]
    v = v * base % MOD
if P == Q:
    print(0)
    exit(0)

for i in range(int(readline())):
    x, y = map(int, readline().split()); x -= 1; y -= 1
    p = A[x]; q = A[y]; r = B[y] - B[x]
    P += r * p - r * q
    if P == Q:
        print(i+1)
        break
    A[x], A[y] = q, p
else:
    print(-1)

Solution (Python):
INF = 2000000000
diff = 0

def update(i, v):
  global diff
  d1 = 0
  d2 = 0
  if A[i-1] > A[i]: d1 += 1
  if A[i] > A[i+1]: d1 += 1
  A[i] = v
  if A[i-1] > A[i]: d2 += 1
  if A[i] > A[i+1]: d2 += 1
  diff += (d2 - d1)

def solve():
    global diff
    for i in range(1, N+1):
        if  A[i-1] > A[i]: diff += 1

    if diff == 0: return 0
    q = int(input())
    for i in range(1, q+1):
        a,b = map(int, input().split())
        v1 = A[a]
        v2 = A[b]
        update(a, v2)
        update(b, v1)
        if diff == 0:  return i

    return -1

N = int(input())
A = list(map(int, input().split()))
A.insert(0, -INF)
A.append(INF)
print(solve())

Solution (Python):
n = int(input())
a_lst = list(map(int, input().split()))
q = int(input())
query = [tuple(map(int, input().split())) for _ in range(q)]
comp = sorted(a_lst)
diff = sum([a_lst[i] != comp[i] for i in range(n)])
if diff == 0:
  print(0)
else:
  for i in range(q):
    x, y = query[i]
    x -= 1
    y -= 1
    diff -= (a_lst[x] == comp[y]) + (a_lst[y] == comp[x]) - (a_lst[x] == comp[x]) - (a_lst[y] == comp[y])
    if diff == 0:
      print(i + 1)
      break
    a_lst[y], a_lst[x] = a_lst[x], a_lst[y]
  else:
    print(-1)