package main

import (
	"sort"
)

func partition(xs []int, left, right, pivotIndex int) int {
	pivot := xs[pivotIndex]
	partitionIndex := left
	xs[pivotIndex], xs[right] = xs[right], xs[pivotIndex]
	for i := left; i < right; i++ {
		if xs[i] < pivot {
			xs[i], xs[partitionIndex] = xs[partitionIndex], xs[i]
			partitionIndex++
		}
	}
	xs[right], xs[partitionIndex] = xs[partitionIndex], xs[right]
	return partitionIndex
}

func medianOfMedians(xs []int, left, right int) int {
	if right-left < 5 {
		sort.Ints(xs[left : right+1])
		return left + (right-left)/2
	}
	groupCount := 0
	for i := left; i < right+1; i += 5 {
		subright := i + 4
		if subright > right {
			subright = right
		}
		m := medianOfMedians(xs, i, subright)
		j := left + (i-left)/5
		// move median to the beginning of the chunk
		xs[m], xs[j] = xs[j], xs[m]
		groupCount++
	}
	return medianOfMedians(xs, left, left+groupCount-1)
}

func quickselect(xs []int, left, right, kth int) int {
	if left == right {
		return xs[left]
	}
	//pivotIndex := left + rand.Intn(right-left+1)
	pivotIndex := medianOfMedians(xs, left, right)
	pivotIndex = partition(xs, left, right, pivotIndex)
	targetIndex := kth - 1
	if targetIndex == pivotIndex {
		return xs[pivotIndex]
	} else if targetIndex < pivotIndex {
		return quickselect(xs, left, pivotIndex-1, kth)
	} else {
		return quickselect(xs, pivotIndex+1, right, kth)
	}
}