##### Canadian Computing Competition: 2005 Stage 1, Senior #5

Pinball is an arcade game in which an individual player controls a silver ball by means of flippers, with the objective of accumulating as many points as possible. At the end of each game, the player's score and rank are displayed. The score, an integer between and , is that achieved by the player in the game just ended. The rank is displayed as " of ". is the total number of games ever played on the machine, and is the position of the score for the just-ended game within this set.

*More precisely, is one greater than the number of games whose score exceeds that of the game just ended.*

#### Input Specification

You are to implement the pinball machine's ranking algorithm. The first line of input contains a positive integer, , the total number of games played in the lifetime of the machine. lines follow, given the scores of these games, in chronological order.

#### Output Specification

You are to output the average of the ranks (rounded to two digits after the decimal) that would be displayed on the board. At least one test case will have . All test cases will have .

#### Sample Input

```
5
100
200
150
170
50
```

#### Sample Output

`2.20`

#### Explanation

The pinball screen would display (in turn):

```
1 of 1
1 of 2
2 of 3
2 of 4
5 of 5
```

The average rank is .

## Comments

This comment is hidden due to too much negative feedback. Click here to view it.

Can we assume no two input are the same?

If they are the same, what should I output?

Inputs are not necessarily distinct

tfw changing all floats to doubles AC's

Round to 2 decimal places?

Output Specification

"...output the average of the ranks (rounded to two digits after the decimal) that...."

Right,sorry.

I implemented BST and still got TLE? Is there something faster?

Read this for more info.

This comment is hidden due to too much negative feedback. Click here to view it.

Your solution is $(O(N^2\ log N)$ because insertion into an ArrayList at an arbitrary position is $O(N)$ time

Really? Okay thanks a lot!

This comment is hidden due to too much negative feedback. Click here to view it.

This comment is hidden due to too much negative feedback. Click here to view it.

This comment is hidden due to too much negative feedback. Click here to view it.

This comment is hidden due to too much negative feedback. Click here to view it.

This comment is hidden due to too much negative feedback. Click here to view it.

This comment is hidden due to too much negative feedback. Click here to view it.

This comment is hidden due to too much negative feedback. Click here to view it.

This comment is hidden due to too much negative feedback. Click here to view it.