Untitled

Предположим мы хотим проверить удовлетворяет ли весь массив искомому требованию. Если это так, то мы можем вывести весь массив как ответ. Иначе один из двух крайних элементов не удовлетворяет нашим требованиям. Из этого можно сделать вывод, что все отрезки содержащие элемент, который не удовлетворяет нашим требованиям будут также некорректными, потому что этот крайний элемент будет оставаться минимумом/максимумом.

 

Из факта выше следует алгоритм: давайте посмотрим на подотрезок [𝑙;𝑟], который изначально равен [1;𝑛]. Если 𝑎𝑙=min(𝑎𝑙,𝑎𝑙+1,…,𝑎𝑟) или 𝑎𝑙=max(𝑎𝑙,𝑎𝑙+1,…,𝑎𝑟), то перейдем к отрезку [𝑙+1;𝑟]. Также необходимо аналогичное рассуждения для 𝑎𝑟. Таким образом мы либо через сколько-то иттераций получим требуемый подотрезок, либо получим 𝑙==𝑟 и ответом будет −1.

 

Пример кода на python:

n = int(input())

a = list(map(int, input().split()))

l = 0

r = n - 1

mn = 1

mx = n

while 0 == 0:

    if l >= r:

        print(-1)

        break

    elif a[l] == mn or a[l] == mx:

        if a[l] == mn:

            mn += 1

        if a[l] == mx:

            mx -= 1

        l += 1

    elif a[r] == mn or a[r] == mx:

        if a[r] == mn:

            mn += 1

        if a[r] == mx:

            mx -= 1

        r -= 1

    else:

        print(l + 1, r + 1)

        break