Challenge: Handshakes, Fast

Lab C++ Beginner 10 points

At a party of n people, everyone shakes hands with everyone else once. Print the number of handshakes using an O(1) formula – n can be a billion, so a double loop is far too slow. Watch out for overflow!

Input

One whole number n (1 ≤ n ≤ 10⁹).

Output

The number of handshakes.

Example

Input

Output

Sample input available Sample output available

Editor

C++

Hints

Each person shakes n - 1 hands, but that counts every handshake twice.

Store n in a long long before multiplying.

Solution explanation

n × (n − 1) / 2 in one step. With n = 10⁹ the product is about 10¹⁸, which fits in a long long.

Show solution

#include <iostream>
using namespace std;

int main() {
    long long n;
    cin >> n;
    cout << n * (n - 1) / 2 << endl;
    return 0;
}

Output

Answer