현권이와 신기한 수열

면접 대비

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

요약

N이 주어질 때 A_N을 구합니다. A_0은 0이고, 각 단계에서 이전 값에서 i를 뺍니다. 다만 결과가 음수이거나 이미 나온 값이면 i를 더합니다.

문제

현권이는 신기한 수열을 찾는 것을 좋아한다. 평소처럼 수열을 찾던 현권이는 재미있는 수열 $A$ 를 하나 발견했다.

수열 $A$ 는 다음 조건을 만족한다.

$A_0 = 0$
$A_i = A_{i-1} - i$ $A_{i} = A_{i - 1} - i$
- 단, 위 조건으로 구한 $A_i$ 가 음수이거나 $A_0, \cdots, A_{i-1}$ 중에 이미 존재하는 값이면, $A_i = A_{i-1} + i$ 이다.

현권이는 이 수열을 구하는 프로그램을 만들고 싶어 한다. 현권이를 도와 $N$ 이 주어졌을 때 $A_N$ 을 구하는 프로그램을 만들어 보자.

첫 번째 줄에 음이 아닌 정수 $N$ 이 주어진다.

첫 번째 줄에 $A_N$ 을 출력한다.

$0 \le N \le 100\,000$