LASTPOS - How many are placed at last positions

no tags 

To keep an array of data in ascending order during insertion sort process, an incoming data has to be inserted somewhere inside the sorted data by shifting bigger data. However if the new data is already bigger than the sorted data, no insertion is necessary, as the data will be appended at end of the list. Count how many data already bigger than the sorted data during the insertion process.

Input

A list of 32-bit integers, one in each line. There will be no more than 99000 data in the input in any test case. You should read all of them until end of input file.

Output

The number of data during the insertion process that were placed at end of the sorted data.

Example

Input:
3
2
5
1
5
9
3

Output: 4

Explanation:
During the process of insertion, value 3 was the first data, so it was appended to an empty list. Before the first value 5 was inserted, the list was "2 3", so it wiould be appended. Yet after some more data, when second value 5 came, the list was "1 2 3 5", so the second 5 would be appended as well. Next came value 9, and the list was "1 2 3 5 5", so the 9 was appended. And the final list became "1 2 3 3 5 5 9" and there were 4 data appended instead of inserted.


hide comments
iammaziz: 2017-09-18 15:58:48

Last edit: 2017-09-18 15:59:02

Added by:Jimmy Tirtawangsa
Date:2017-08-26
Time limit:1s-2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All