import random

frogs = []
frogs_sorted = []
n = int(input("Enter the number of frogs: "))
lower_bound = int(input("Enter the lower bound: "))
upper_bound = int(input("Enter the upper bound: "))

for i in range(n+1):
    if i == 0:
        frogs.append(0)
        frogs_sorted.append(0)
    else:
        number = random.randint(lower_bound, upper_bound)
        frogs.append(number)
        frogs_sorted.append(number)
print(frogs)

# Helper variables
moves = 0
p = 0
q = 0

frogs_sorted = sorted(frogs_sorted, reverse=True)
if n == 1:
    total_moves = 0
else:
    while True:
        if frogs[1:] == frogs_sorted[:n]:
            break
        # Move from left to right
        if q == 0:
            if frogs[p] == frogs[-2]:
                frogs[p], frogs[p+1] = frogs[p+1], frogs[p]
                p += 1
            elif frogs[p] == frogs[-1]:
                q = 1
            elif frogs[p+2] > frogs[p+1]:
                frogs[p], frogs[p+2] = frogs[p+2], frogs[p]
                p += 2
            else:
                frogs[p], frogs[p+1] = frogs[p+1], frogs[p]
                p += 1
        # Move from right to left
        if q == 1:
            if frogs[p] == frogs[1]:
                frogs[p], frogs[p-1] = frogs[p-1], frogs[p]
                p -= 1
            elif frogs[p] == frogs[0]:
                q = 0
            elif frogs[p-2] < frogs[p-1]:
                frogs[p], frogs[p-2] = frogs[p-2], frogs[p]
                p -= 2
            else:
                frogs[p], frogs[p-1] = frogs[p-1], frogs[p]
                p -= 1
        moves += 1
        print(frogs)
    total_moves = moves
print("Total moves: ", total_moves)