Двійковий пошук
Двійковий пошук — це алгоритм, який використовується для пошуку заданого елементу у відсортваному масиві. Розглянемо наступний псевдокод двійкового пошуку ("/" позначає ділення націло):
вход: a[0..n-1], x
l=0;
r=n;
while ( l < r-1 ) {
m=(l+r)/2;
if(a[m]<=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 у якості аргументів.
Вхідні дані
Вхідний файл містить одне ціле число n (1 ≤ n ≤ 1000).
Вихідні дані
Виведіть одне ціле число — відповідь на поставлену задачу.