Двоичный поиск

시간 제한2초메모리 제한1024 MB

요약

1부터 n까지의 값을 담은 길이 n 배열과 1부터 n까지의 값 x 쌍 중 주어진 이분 탐색이 true를 반환하는 쌍의 수를 센다.

난이도: 보통10점 중 7점
유형: 조합론, 동적 계획법, 수학
정답자: 아직 제출이 없습니다

문제

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

вход: 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$ ).

출력

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

예제2

예제 1
입력
```
1
```
예상 출력
```
1
```
예제 2
입력
```
2
```
예상 출력
```
5
```