BAISED  Biased Standings
Usually, results of competitions are based on the scores of participants. However, we are planning a change for the next year of IPSC. During the registration each team will be able to enter a single positive integer : their preferred place in the ranklist. We would take all these preferences into account, and at the end of the competition we will simply announce a ranklist that would please all of you.
But wait... How would that ranklist look like if it won't be possible to satisfy all the requests?
Suppose that we already have a ranklist. For each team, compute the distance between their preferred place and their place in the ranklist. The sum of these distances will be called the badness of this ranklist.
Problem specification
Given team names and their preferred placements find one ranklist with the minimal possible badness.
Input specification
The first line of the input file contains an integer T specifying the number of test cases. Each test case is preceded by a blank line.
Each test case looks as follows: The first line contains N : the number of teams participating in the competition. Each of the next N lines contains a team name (a string of letters and numbers) and its preferred place (an integer between 1 and N, inclusive). No two team names will be equal.
Output specification
For each of the test cases output a single line with a single integer : the badness of the best ranklist for the given teams.
Example
Input: 2 7 noobz 1 llamas 2 Winn3rz 2 5thwheel 1 NotoricCoders 5 StrangeCase 7 WhoKnows 7 3 ThreeHeadedMonkey 1 MoscowSUx13 1 NeedForSuccess 1 Output: 5 3Explanation:
In the first test case, one possible ranklist with the minimal badness is:
1. noobz 2. llamas 3. Winn3rz 4. 5thwheel 5. NotoricCoders 6. WhoKnows 7. StrangeCase
In the second test case all ranklists are equally good.
Note: the input file will not exceed 5MB.hide comments
shivamyadav00:
20201019 06:22:42
In python, make sure to consider the empty line between inputs (before each test case). Cost me a runtime error!. 

tarun_28:
20201005 10:25:48
use vector of pairs;) 

bala_24:
20200925 10:05:01
How can we prove that sorting of preferred ranks would give us optimal answer ? 

codephilic:
20200822 13:48:46
This problem can be solved in O(n) time using counting sort but the rank is too high so it is preferable to use


avsd_47:
20200815 11:57:20
Try to solve it in O(n) time. 

noobmaster__69:
20200312 14:47:35
Can anyone tell what is wring with this approach? I'm making a boolean array(size n) with all values set to 0(1 indexed) . In each input,I go to the kth (k==preferred place) index in the array and if it is 0 then i do nothing. But is it is 1 then I find the minimum distance among the left and right of the kth index where arr[index]=zero and count the distance and also set arr[index] to 1. 

pratiikgoogler:
20200311 15:13:54
Why does SPOJ have this bad habit of not providing constraints? Took me a WA for not using long long :( 

yash995:
20191228 12:45:47
can anyone provide me the test cases with the answers 

hetp111:
20190906 15:56:04
Constraints ??!!!??? 

pistachio:
20190317 20:42:31
1 <= N <= 100000 and in some tests cases the badness of the best ranklist could be over 2^31, thus use long if needed 
Added by:  Fudan University Problem Setters 
Date:  20071201 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: C99 ERL JSRHINO 
Resource:  IPSC 2006 