LCC/Moose '20 Contest 2 S1 - Momentum

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 1.0s
Memory limit: 64M

Author:
Problem type

Mr. Bouttell is teaching momentum in class and he wants to demonstrate how different objects interact when they collide. He has N objects, with the ith object having a momentum of a_i. Mr. Bouttell wants to demonstrate that an object travelling at a higher momentum will be able to continue going if it collides with an object with a strictly lower momentum. Mr. Bouttell wants to know how many pairs of objects will collide in such a way that the first object will be able to continue going.

Can you help him?

Input Specification

The first line of input will contain a single integer, N (1 \leq N \leq 10^5)

The next line of input will consist of N space separated integers, where the ith integer denotes a_i (-10^9 \leq a_i \leq 10^9).

Output Specification

A single line containing the number of pairs of objects will collide in such a way that the first object will be able to continue going.

Subtasks

Subtask 1 (10%)

1 \leq N \leq 7

Subtask 2 (20%)

1 \leq N \leq 1000

Subtask 3 (10%)

-10^5 \leq a_i \leq 10^5

Subtask 4 (60%)

No further constraints.

Sample Input

3
1 2 3

Sample Output

3

Comments

There are no comments at the moment.