Задача с контеста Тинькофф

Даны n нестрого возрастающих массивов Ai и m нестрого убывающих массивов Bj. Все массивы имеют одну и ту же длину l. Далее даны q запросов вида (i, j), ответ на запрос — такое k, что max(A[i][k], B[j][k]) минимален. Если таких k несколько, можно вернуть любое.

(1 <= n, m <= 900)
(1 <= l <= 900)
(1 <= q <= n * m)

Решение:
По факту в запросе нам дают два вектора и просят найти минимальный максимум.
Посмотрим на последовательность max(A[i][k], B[j][k]) заметим, что у нас последовательность сначала невозрастает, а потом неубывает.
Если бы все числа были бы различны то мы могли бы видеть такой график:
\ /
\ /
\ /
\ /
\/
Вам нужно найти нижний угол. Эту позицию вы можете найти бинарным поиском сдвигая левую границу если a[mid - 1] > a[mid], но все усложняется тем, что у нас могут быть одинаковые символы и наш график мог выглядеть:
/
\ ———- /
\—— /
\ /
\——/
Теперь именно так бинарить нельзя и наше решение ломается.
Но давайте лучше посмотрим на max(A[i][k], B[j][k]) где первый массив неубывает, а второй невозрастает и по факту мы хотели бы найти самую левую позицию t, такую что A[i][t] >= B[j][t] - а такую штуку мы можем бинарить. Нужно просто сдвигать правую границу бинарного поиска, если A[i][mid] >= B[j][mid].

Второе возможное решение - это тернарный поиск, но сложно будет учитывать равенства.

Время работы O(q * log(l))