Halfway Point

Time limit1sMemory limit512 MB

Summary

Given n, find the value printed when the pair-comparison loop reaches its halfway point (the last item index printed there).

Level: Medium4 of 10
Topics: Binary search, Math, Prefix sum, Implementation
Solved: No attempts yet

Problem

A friend of yours wrote a program that compares every pair of $n$ items exactly once. The program first prints $1$ and compares item $1$ with items $2, 3, 4, \dots, n$ . It then prints $2$ and compares item $2$ with items $3, 4, 5, \dots, n$ . It goes on the same way until every pair has been compared exactly once. If it compares item $x$ with item $y$ , it never compares item $y$ with item $x$ later, and it never compares an item with itself.

Your friend wants to know the moment the program is halfway done. If the total number of comparisons is odd, that is the moment it performs the middle comparison. If the total is even, that is the moment it performs the first of the two middle comparisons.

Find the last number printed when the program is halfway done.

Earlier items take part in more comparisons than later ones, so the answer is not $n/2$ .

Input

The first line contains an integer $n$ . ( $2 \le n \le 10^9$ )

Output

Print on one line the last number your friend's program prints when it is halfway done.

Examples5

Example 1
Input
```
4
```
Expected output
```
1
```
Example 2
Input
```
7
```
Expected output
```
2
```
Example 3
Input
```
10
```
Expected output
```
3
```
Example 4
Input
```
1919
```
Expected output
```
562
```
Example 5
Input
```
290976843
```
Expected output
```
85225144
```