#셰이커 정렬

from typing import MutableSequence

def shaker_sort(a: MutableSequence) -> None:
	left = 0
	right = len(a) - 1
	last = right
	while left < right:
		for j in range(right, left, -1):
			if a[j - 1] > a[j]:
				a[j - 1], a[j] = a[j], a[j - 1]
				last = j
		left = last

		for j in range(left, right):
			if a[j] > a[j + 1]:
				a[j], a[j + 1] = a[j + 1], a[j]
				last = j
		right = last
4f4c9eee434467ad46760987069d6857237176a6
<mask token>

<mask token>


def shaker_sort(a: MutableSequence) ->None:
    left = 0
    right = len(a) - 1
    last = right
    while left < right:
        for j in range(right, left, -1):
            if a[j - 1] > a[j]:
                a[j - 1], a[j] = a[j], a[j - 1]
                last = j
        left = last
        for j in range(left, right):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
                last = j
        right = last

from typing import MutableSequence


def shaker_sort(a: MutableSequence) ->None:
    left = 0
    right = len(a) - 1
    last = right
    while left < right:
        for j in range(right, left, -1):
            if a[j - 1] > a[j]:
                a[j - 1], a[j] = a[j], a[j - 1]
                last = j
        left = last
        for j in range(left, right):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
                last = j
        right = last

#셰이커 정렬

from typing import MutableSequence

def shaker_sort(a: MutableSequence) -> None:
	left = 0
	right = len(a) - 1
	last = right
	while left < right:
		for j in range(right, left, -1):
			if a[j - 1] > a[j]:
				a[j - 1], a[j] = a[j], a[j - 1]
				last = j
		left = last

		for j in range(left, right):
			if a[j] > a[j + 1]:
				a[j], a[j + 1] = a[j + 1], a[j]
				last = j
		right = last