/*
-- ПРИНЦИП РАБОТЫ --
Идея поиска индекса элемента в отсортированном сломанном массиве в следующем:
Если разделить массив на 2 части, то как минимум одна часть будет отсортирована,
а вторая будет либо отсортирована (если разбиением попали на стык "сломанной" части)
либо не отсортирована.
Проверить наличие элемента в отсортированной части легко: искомый будет не меньше первого элемента и не больше последнего
Если элемент находится в отсортированной части, то дальше его можно найти бинарным поиском

Если же элемента нет в отсортированной части, а значит можно рекурсивно запустить поиск

Поэтому алгоритм следующий:
1. Находим средний элемент (при чётном количестве элементов -- последний из левой половины)
2. Если он совпадает с искомым -- поиск завершён
3. Если он не совпадает, то проверяем левую часть на отсортированность
3.1. Если левая часть отсортирована
3.1.1. проверяем в ней наличие искомого элемента. Если находится -- запускаем бинарный поиск, конец алгоритма
3.1.2. элемент не находится в левой отсортированной части -- значит он в правой части
3.1.3. проверяем отсортированность правой части
3.1.3.1. правая часть отсортирована -- запускаем бинарный поиск, конец алгоритма
3.1.3.2. правая часть не отсортирована -- рекурсивно запускаем поиск по сломанному массиву
3.2. Если левая часть сломана
3.2.1. Значит правая часть -- отсортирована
3.2.1.1. проверяем в ней наличие искомого элемента. Если находится -- запускаем бинарный поиск, конец алгоритма
3.2.1.2. в правой части нет искомого -- значит рекурсивно запускаем поиск по левой сломанной части

-- ДОКАЗАТЕЛЬСТВО КОРРЕКТНОСТИ --

По условию задачи, изначально массив был отсортирован по возрастанию, но записан со сдвигом индексов по кругу.
Т.е. с начала массива элементы возрастают, потом происходит "прыжок" вниз, после чего элементы снова возрастают до конца массива
После разделения массива со сломанной сортировкой, одна часть будет отсортирована.
Действительно, будь это иначе, то после "склейки" массивов обратно, в итоговом массиве окажется 2 "прыжка", что противоречит условию задачи
Таким образом, после разделения поиск будет осуществлён либо в отсортированной части, либо рекурсивно в сломанной.

На каждом уровне рекурсии сломанная часть уменьшается (как минимум, проверяем середину и она в дальнейшем поиске не участвует)
Таким образом, в худшем случае, разделение изначального массива будет происходить, пока не останется массив из двух или трёх элементов
между которыми и происходит "разрыв". Последующее разделение приведёт к поиску в массиве из нуля или одного элемента, который по определению отсортирован

Таким образом, весь поиск сведётся к поиску в отсортированном массиве
Корректность поиска в отсортированной части в доказательстве не нуждается (это не тема данной задачи)

-- ВРЕМЕННАЯ СЛОЖНОСТЬ --
На вход подаётся n элементов. Каждую итерацию массив делится примерно пополам (зависит от чётности кол-ва элементов)
И дальнейшая обработка происходит только на половине элементов.
Итого, у алгоритма временная сложность O(log(n))

-- ПРОСТРАНСТВЕННАЯ СЛОЖНОСТЬ --
Входные параметры не учитываются, поэтому они на временную сложность не влияют
В алгоритме на каждой итерации используется 3 дополнительных переменных, хранящие указатели на левый, правый и средний элемент обрабатываемого подмассива. Это константная сложность O(1)
Кроме того, в алгоритме используется рекурсия. Т.к. на каждой итерации рекурсии обрабатывается примерно половина объёма предыдущей итерации, зависимость глубины рекурсии от входных данных log_2 (n)
Итого, у алгоритма пространственная сложность
- если учитывать стек вызовов, то O(log(n))
- если считать только кучу, то  O(1)

--ПОСЫЛКА--
https://contest.yandex.ru/contest/23815/run-report/91532453/
*/

object Solution {
    fun brokenSearch(arr: IntArray, k: Int): Int {
        // Your code
        // ヽ(´▽`)/
        return arr.brokenSearch(k, 0, arr.lastIndex);
    }

    /**
     * Ищет индекс в отсортированном массиве
     */
    private fun IntArray.search(element: Int, left: Int, right: Int): Int {

        // Базовый случай: период поиска сужен до 1 элемента
        if (left == right) {
            //если он -- искомый, то возвращаем индекс
            if (this[left] == element) return left
            //иначе возвращаем -1, т.к. элемент не найден
            return -1
        }

        // Если промежуток пустой
        if (left > right) return -1

        val middle = left + ((right - left) shr 1)

        return when {
            // Если искомый слева от середины, то рекурсивно вызываем поиск слева до среднего не включая
            element < this[middle] -> search(element, left, middle - 1)
            // иначе искомый справа, рекурсивно вызываем поиск справа от среднего до конца
            else -> search(element, middle, right)
        }
    }

    /**
     * Ищет индекс в сломанном массиве
     */
    private fun IntArray.brokenSearch(element: Int, left: Int, right: Int): Int {
        // Базовый случай: изначально в массиве 1 элемент
        if (left == right) {
            // если он -- искомый, то возвращаем индекс
            if (this[left] == element) return left
            // иначе возвращаем -1, т.к. элемент не найден
            return -1
        }
        val middle = left + ((right - left) shr 1)

        // Середина разбивает массив на два подмассива, как минимум один из которых заведомо отсортирован
        // Если у левого отрезка сохранена сортировка концов, то он в целом отсортирован
        return if (this[left] <= this[middle]) {
            // левый отсортирован
            if (element in this[left] until this[middle]) {
                // искомый находится в левом отсортированном подмассиве
                search(element, left, middle - 1)
            } else {
                // искомый находится в правом подмассиве
                // середина могла разбить на два отсортированных массива, проверяем правый
                if (this[middle] <= this[right]) {
                    // правый отсортирован
                    search(element, middle, right)
                } else {
                    // правый не отсортирован
                    brokenSearch(element, middle, right)
                }
            }
        } else {
            // левый подмассив не отсортирован
            // значит правый точно отсортирован
            if (element in this[middle]..this[right]) {
                // искомый находится в правом отсортированном подмассиве
                search(element, middle, right)
            } else {
                // искомый находится в левом неотсортированном подмассиве
                brokenSearch(element, left, middle - 1)
            }
        }
    }
}