Двійковий пошук

Двійковий пошук — це алгоритм, який використовується для пошуку заданого елементу у відсортованому масиві. Розглянемо наступний псевдокод двійкового пошуку ($/$ позначає ділення націло):

вхід: a_0, a_1, \ldots, a_{n-1}, $x$

l = 0;

r = n;

while (l < r - 1) {

m = (l + r) / 2;

if (a_m \leq x)

l = m;

else

r = m;

}

if (a_l == x)

return true;

else

return false;

Іноді виявляється, що двійковий пошук знаходить входження деякого елемента в масиві навіть якщо масив не відсортовано. Вам задано число $n$. Потрібно знайти кількість пар $⟨a,x⟩$, де $a$ представляє собою масив довжини $n$, який містить цілі числа від $1$ до $n$, а $x$ — ціле число від $1$ до $n$, таких, що наведена процедура повертає true, якщо її запустити на масиві $a$ та числі $x$ у якості аргументів.