Двоичный поиск
Двоичный поиск — это алгоритм, который используется для поиска заданного элемента в отсортированном массиве. Рассмотрим следующий псевдокод двоичного поиска ("/" означает деление нацело):
вход: 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).
Выходные данные
Выведите одно целое число — ответ на поставленную задачу.