29497번 - Двоичный поиск 다국어

문제

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

вход: 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$. Требуется найти количество пар $\langle a, x\rangle,ドル где $a$ представляет собой массив длины $n,ドル содержащий целые числа от 1 до $n,ドル а $x$ --- целое число от 1 до $n,ドル таких что приведенная процедура возвращает "true", если ее запустить на массиве $a$ и числе $x$ в качестве аргументов.

입력

Входной файл содержит одно целое число $n$ (1ドル \le n \le 1000$).

출력

Выведите одно целое число --- ответ на поставленную задачу.

제한

힌트