Challenge: Handshakes, Fast

Lab Python Beginner 10 points

At a party of n people, everyone shakes hands with everyone else exactly once. Print how many handshakes happen. A double loop would be O(n²) – find the O(1) formula instead, because n can be up to one billion.

Input

One whole number n (1 ≤ n ≤ 1,000,000,000).

Output

The number of handshakes.

Example

Input

Output

Sample input available Sample output available

Editor

Python

Hints

Each of the n people shakes n - 1 hands.

But that counts every handshake twice (A with B and B with A).

Solution explanation

n × (n − 1) counts each handshake twice, so divide by 2. One calculation: O(1), however big n is.

Show solution

n = int(input())
print(n * (n - 1) // 2)

Output

Answer