Challenge: Gauss's Shortcut

Lab Java Beginner 10 points

Print 1 + 2 + 3 + … + n. But n can be up to 2 billion, so a loop is too slow. Use the O(1) formula n × (n + 1) / 2 – and choose the right type so it doesn't overflow.

Input

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

Output

The sum.

Example

Input

Output

Sample input available Sample output available

Editor

Java

Hints

Read n with sc.nextLong(), not nextInt().

n × (n + 1) for n = 2 billion is about 4 × 10¹⁸ – it fits in a long.

Solution explanation

The young mathematician Gauss noticed that 1 + 100, 2 + 99, 3 + 98 … all make 101, giving n × (n + 1) / 2 in a single step. A formula beats a loop: O(1) instead of O(n).

Show solution

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        System.out.println(n * (n + 1) / 2);
    }
}

Output

Answer