Hyeongwon and the Curious Sequence

Interview

Time limit0.1sMemory limit1024 MB

Summary

Given N, compute A_N, where A_0 is 0 and each step subtracts i from the previous value unless the result is negative or already used, in which case it adds i.

Level: Easy3 of 10
Topics: Simulation, Hash map
Solved: No attempts yet

Problem

Hyeongwon likes looking for curious sequences. While searching as usual, he found an interesting sequence $A$ .

Sequence $A$ satisfies the following conditions.

$A_0 = 0$
$A_i = A_{i-1} - i$ $A_{i} = A_{i - 1} - i$
- However, if the $A_i$ computed by the rule above is negative or already appears among $A_0, \cdots, A_{i-1}$ , then $A_i = A_{i-1} + i$ .

Hyeongwon wants a program that computes the sequence. Help him write a program that, given $N$ , finds $A_N$ .

Input

The first line contains a non-negative integer $N$ .

Output

Print $A_N$ on the first line.

Constraints

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

Examples3

Example 1
Input
```
2
```
Expected output
```
3
```
Example 2
Input
```
4
```
Expected output
```
2
```
Example 3
Input
```
16279
```
Expected output
```
34154
```