In the city of the future, there are many small islands (districts). Now, we want to build some bridges between these islands. Each bridge is a passage between two islands. There is a rule: if there is a bridge between island A and island B, and a bridge between island B and island C, then there cannot be a bridge between island A and island C. That is, for any three islands in the city, it is not allowed to have bridges between all pairs of them. Under this rule, we want to maximize the number of bridges, without needing to consider the specific spatial structure.

Input

The input contains only one line, which contains a single non-negative integer $n$, where $0 \le n \le 1000$, representing the number of islands.

Output

The output contains only one line, representing the maximum number of bridges that can be built.

Examples

Input 1

6

Output 1

9

Input 2

11

Output 2

30