[Question]
  [
Two lists `A` and `B` are congruent if they have the same length, and elements that compare equal in `A` compare equal in `B`.
In other words, given any two valid indices `x` and `y`:
* If `A[x] = A[y]`, then `B[x] = B[y]`.
* If `A[x] != A[y]`, then `B[x] != B[y]`.
For example, the lists `[1, 2, 1, 4, 5]` and `[0, 1, 0, 2, 3]` are congruent.
## The Task
Given a nonempty list of *nonnegative* integers `A`, return a new list of *nonnegative* integers `B` such that is congruent to `A`, while minimizing the sum of the integers in `B`.
There are potentially many possible valid outputs. For example, in the list `[12, 700, 3]`, any permutation of `[0, 1, 2]` would be considered valid output.
## Test Cases
```
Format:
input ->
one possible valid output
[1 2 1 4 5] ->
[0 1 0 2 3] (this is the example given above)
[3 2 2 1 5 7 2] ->
[1 0 0 2 3 4 0]
[8 8 8 8 8] ->
[0 0 0 0 0]
[2] ->
[0]
[8 6 8 4 6 8 2 4 6 8 0 2 4 6 8] ->
[0 1 0 2 1 0 3 2 1 0 4 3 2 1 0]
[14 1] ->
[1 0]
[19 6 4 9 14 17 10 9 6 14 8 14 6 15] ->
[8 0 3 2 1 7 5 2 0 1 4 1 0 6]
[15] ->
[0]
[1 18 4 8 6 19 12 17 6 13 7 6 8 1 6] ->
[1 8 3 2 0 9 5 7 0 6 4 0 2 1 0]
[9 10 11 9 7 11 16 17 11 8 7] ->
[2 4 0 2 1 0 5 6 0 3 1]
[1 3 16 19 14] ->
[0 1 3 4 2]
[18 8] ->
[1 0]
[13 4 9 6] ->
[3 0 2 1]
[16 16 18 6 12 10 4 6] ->
[1 1 5 0 4 3 2 0]
[11 18] ->
[0 1]
[14 18 18 11 9 8 13 3 3 4] ->
[7 1 1 5 4 3 6 0 0 2]
[20 19 1 1 13] ->
[3 2 0 0 1]
[12] ->
[0]
[1 14 20 4 18 15 19] ->
[0 2 6 1 4 3 5]
[13 18 20] ->
[0 1 2]
[9 1 12 2] ->
[2 0 3 1]
[15 11 2 9 10 19 17 10 19 11 16 5 13 2] ->
[7 2 0 5 1 3 9 1 3 2 8 4 6 0]
[5 4 2 2 19 14 18 11 3 12 20 14 2 19 7] ->
[5 4 0 0 2 1 9 7 3 8 10 1 0 2 6]
[9 11 13 13 13 12 17 8 4] ->
[3 4 0 0 0 5 6 2 1]
[10 14 16 17 7 4 3] ->
[3 4 5 6 2 1 0]
[2 4 8 7 8 19 16 11 10 19 4 7 8] ->
[4 1 0 2 0 3 7 6 5 3 1 2 0]
[15 17 20 18 20 13 6 10 4 19 9 15 18 17 5] ->
[0 1 3 2 3 9 6 8 4 10 7 0 2 1 5]
[15 14 4 5 5 5 3 3 19 12 4] ->
[5 4 2 0 0 0 1 1 6 3 2]
[7 12] ->
[0 1]
[18 5 18 2 5 20 8 8] ->
[2 0 2 3 0 4 1 1]
[4 6 10 7 3 1] ->
[2 3 5 4 1 0]
[5] ->
[0]
[6 12 14 18] ->
[0 1 2 3]
[7 15 13 3 4 7 20] ->
[0 4 3 1 2 0 5]
[10 15 19 14] ->
[0 2 3 1]
[14] ->
[0]
[19 10 20 12 17 3 6 16] ->
[6 2 7 3 5 0 1 4]
[9 4 7 18 18 15 3] ->
[4 2 3 0 0 5 1]
[7 4 13 7] ->
[0 1 2 0]
[19 1 10 3 1] ->
[3 0 2 1 0]
[8 14 20 4] ->
[1 2 3 0]
[17 20 18 11 1 15 7 2] ->
[5 7 6 3 0 4 2 1]
[11 4 3 17] ->
[2 1 0 3]
[1 9 15 1 20 8 6] ->
[0 3 4 0 5 2 1]
[16 13 10] ->
[2 1 0]
[17 20 20 12 19 10 19 7 8 5 12 19] ->
[7 2 2 1 0 6 0 4 5 3 1 0]
[18 11] ->
[1 0]
[2 16 7 12 10 18 4 14 14 7 15 4 8 3 14] ->
[3 9 2 7 6 10 1 0 0 2 8 1 5 4 0]
[5 7 2 2 16 14 7 7 18 19 16] ->
[3 0 1 1 2 4 0 0 5 6 2]
[8 6 17 5 10 2 14] ->
[3 2 6 1 4 0 5]
```
This is [code-golf](/questions/tagged/code-golf "show questions tagged 'code-golf'"), so the shortest valid submission (counted in bytes) wins.
  
[Answer]
# [Python 2](https://docs.python.org/2/), ~~62~~ 54 bytes
```
lambda L:map(sorted(set(L),key=L.count)[::-1].index,L)
```
[Try it online!](https://tio.run/##VVNBbuMwDDxvXpFbEoAtTFmy7ADtsSf/oO0hu3HQYjdOkLpA@/qUQ1FyFjYsmSJnOCR1/p7eTqO7Hh5erv92x9/73bLfHnfn9cfpMg379ccwrfsN/R2@H/r7P6fPcdo8b7d3/Hr/Pu6HL@o31/1wWD6J03bx63x5H6fl6mVcUU@ru0dsDnK0WDytn5kcMXkKrxv81vILQ6BILplasif9FmsjNq9fZ2uVd8mFPbHtOrF66gimSFwRDPLT4iM7Yy8rMbDBIaHsECTbmqLyMDXJrwMUs6BFLNwoOotLzEC1WsFsliJE4JCSQcGrAW2jfBWE2AmymRW1@oKzRUZ4DNpVSoSnNn9X9HhywERsELeSghhcVdSAO8cEsDhKGjurGzYqNIDcXIMAa9tSgTW9WqEqJcZBLBxIL79a2TYLYHVPVYyCaSqctgJ@IGgUQTPxMM7ZRuVr9Vujjiq4g4KgWUUKs7fH0OmDEqY2Wx6i1JVuaaiTRWBL73yCj4i0GqQldc@XjkXl1iZhoqtZaPhvKnwZVDmDAK2MqiizBgRrf8i1QZkwl3M4AEpWbW68necSsU7JzSVj3EEJK3ObipZE34youFS3WJZqHhI0KSRLKSBzbqMARJtuvV@sr5YIHa5LOTQx0gB1SLq7Ugu9JRFMuPKIuv4A "Python 2 – Try It Online")
Edit: saved 8 bytes via map thanx to Maltysen
[Answer]
# Pyth - ~~12~~ ~~11~~ 10 bytes
```
XQ_o/QN{QU
```
[Test Suite](http://pyth.herokuapp.com/?code=XQ_o%2FQNK%7BQUK&test_suite=1&test_suite_input=%5B1%2C+2%2C+1%2C+4%2C+5%5D%0A%5B8%2C+6%2C+8%2C+4%2C+6%2C+8%2C+2%2C+4%2C+6%2C+8%2C+0%2C+2%2C+4%2C+6%2C+8%5D&debug=0).
[Answer]
# [Japt](https://github.com/ETHproductions/japt), 11 bytes
```
£â ñ@è¦XÃbX
```
[Test it online!](http://ethproductions.github.io/japt/?v=1.4.5&code=o+Ig8UDopljDYlg=&input=WzE5IDYgNCA5IDE0IDE3IDEwIDkgNiAxNCA4IDE0IDYgMTVd)
### Explanation
```
 £   â ñ@  è¦ XÃ bX
UmX{Uâ ñX{Uè!=X} bX}   Ungolfed
                       Implicit: U = input array
UmX{               }   Map each item X in the input to:
    Uâ                   Take the unique items of U.
       ñX{     }         Sort each item X in this by
          Uè!=X            how many items in U are not equal to X.
                         This sorts the items that occur most to the front of the list.
                 bX      Return the index of X in this list.
                       Implicit: output result of last expression
```
[Answer]
# [J](http://jsoftware.com/), 11 bytes
```
i.~~.\:#/.~
```
[Try it online!](https://tio.run/##y/r/P03B1kohU6@uTi/GSllfr46LKzU5I18hTcFQwQiITRRM//8HAA "J – Try It Online")
## Explanation
```
i.~~.\:#/.~  Input: array A
       #/.~  Frequency of each unique character, sorted by first appearance
   ~.        Unique, sorted by first appearance
     \:      Sort down the uniques using their frequencies
i.~          First index in that for each element of A
```
[Answer]
# [Röda](https://github.com/fergusq/roda), 55 bytes
```
{|l|l|indexOf _,[sort(l)|count|[[-_2,_1]]|sort|_|[_2]]}
```
[Try it online!](https://tio.run/##bVVda9tAEHyOfsWSJwcS0J3uJDmQQl8KoYX8ANWYkCjF4NhBtqEQ57enN7N7kgJFRlJ0@zE7O7sZ9s@Pn@/FxYvc3snvz/fzNl2b3XP/9@FF1tfdYT8cF9ur89P@tDueu@5m7a/XbrU64@C8Pndrv1p9fH4UxevjZieItB9ks3s7Ha9lfzryuZbnfXFxMfSH0/aIRC@L7vC23RwXNOzc7U1YXclZ3h6HQ3@/O/Z/@mGxvuK3w@l1cZW8n/bD0D/RXX01Opzd/5xnrm/DZneUy4efl7J5kU4MyJ3kmCvpt4deLtXwx/f7X5fFxfN@1xcfn10lPl1OojTiV3LzreiclOnyUkmQclUUXSt26XkpduHMfMyuTlaBd2/PMr9lX8dPuFf2DPkNMVwQN8Lgh2XyDrIUnDTiSsGH9EeLW3qLat6OEZtUjBdkCoxfM0ycAXXigBN4U3jnETi9VtIQs0suBqFlTOQEQSWhlBPaJfA4l44bPFxNiHBrNIKf7FOEmhidQqhojromakC55/HIdqahIgkGrNKgPKgZh7V4wAkTerQ186tRUPmYLvPd8ocqWpCAyzClYhgEIWqVBZteEjiuKgPyPNaY/ivXqSagQJKYHHN@D8gMHa3CZOHLiQ1vFKMwn/mcGIzA7EV7sDRx4IWNiCjF5zI8@QfBS969CZUQUR@nQEVGLiomLQkeB9bPyH5qR9H0CpRlUdeGF7TkH7XVZj4rc1cx5A4yi2qnAR@TrVnZqFGyiAagNfOw4ICP6hQMCliCmCMKGbsfkQJFtbyjpxRMirFkb1oYxLkePSnTuU62jdUec7xAlJGJKpumMHHlrVxopUY4@KVG@a8ibIXJPSa3nDaNtz1EjGoaFHNDFZhRRYUaS/M515EIc80jnmGIKnawN6kuZMKsxFI1O5tSPwowzGVOGYJVdpzU2hyihQ1BciepSJDVBi/mjgcrllJVkIFbaY5@zIZ8IwnVfCu1eeTyHmBY@uX2Ow7vbOlHykWpzrrU4XTjKuPS1plWuWiz6gxP1R3nmym5lzP3CYMxlYcXqo76ZRpZzVgTkwq5NLW4r/8jPMahsf3H1e74Y5MDl7gbJ3DJdtR5bEvuAl1ytg0sd60htE/LsZ2VydnbLHNG878/jA@FMEuY95xK6h8 "Röda – Try It Online")
[Answer]
# [Haskell](https://www.haskell.org/), ~~93~~ ~~91~~ 85 bytes
```
import Data.List
f a=[i|x<-a,(i,y:_)<-zip[0..]$sortOn((0-).length)$group$sort a,x==y]
```
[Try it online!](https://tio.run/##Hcq9CsIwFEDh3ae4Q4YEbkIVXaTZHAUfIAS5Q38utmlIIrTiu8ficpbvjJRf3TTVynNcUoEbFTJ3zuXQA1nH37XVhJJxuz5Vqz8cXWOMF3mfH0HKRiszdWEooxJDWt7xL0C4Wrv5OhMHsBAThwICenBHhBPC3jPCxdcf "Haskell – Try It Online")
EDIT: Thanks to @Laikoni for taking off 6 bytes!
Not very short but I can't think of anything else. The idea is to iterate over the array (`x<-a`) and perform a lookup in a tuple list (`(i,y:_)<-`...`,x==y`) that assigns a nonnegative integer to each unique element in the input based on how common it is. That tuple list is generated by first `sort`ing the input, `group`ing it into sublists of equal elements, sorting that list by the length of the sublists (`sortOn((0-).length)`; length is negated to sort into "descending" order), then finally zipping it with an infinite list incrementing from 0. We use pattern matching to extract the actual element fromm the sublist into `y`.
[Answer]
# Mathematica, 94 bytes
```
(s=First/@Reverse@SortBy[Tally[j=#],Last];For[i=1,i<=Length@s,j=j//.s[[i]]->i+5!;i++];j-5!-1)&
```
  
[Try it online!](https://tio.run/##RcixCsIwEADQ3a@wCKL0akk1ONRIcOjUQdQtZAiS2gu1hVwQivTbo06@8T1NaPFOsRFxRaJCTyGXF/uynqy8Dj6cRnUzXTcqJxYaakNBl9XgFQoGeBC17R@hlQROuDzfkFKodXbElCclpqkuXcaTjK2X8eyxD3PZqDeDAhjsgE969t/td3/PYQ/FpOMH "Mathics – Try It Online")
[Answer]
# CJam, ~~17~~ 14 bytes
-3 bytes thanks to Peter Taylor
This is a golfed version of the program I used to generate the testcases.
```
{_$e`$W%1f=f#}
```
This is an anonymous block that expects input as an array on top of the stack and outputs an array on top of the stack.
Explanation:
```
{_$e`$W%1f=f#} Stack:                  [1 2 1 4 5]
 _             Duplicate:              [1 2 1 4 5] [1 2 1 4 5]
  $            Sort:                   [1 2 1 4 5] [1 1 2 4 5]
   e`          Run-length encode:      [1 2 1 4 5] [[2 1] [1 2] [1 4] [1 5]]
     $         Sort lexicographically: [1 2 1 4 5] [[1 2] [1 4] [1 5] [2 1]]
      W%       Reverse:                [1 2 1 4 5] [[2 1] [1 5] [1 4] [1 2]]
        1f=    Second element of each: [1 2 1 4 5] [1 5 4 2]
           f#  Vectorized indexing:    [0 3 0 2 1]
```
[Answer]
# TI-BASIC, 66 bytes
```
Ans+max(Ans+1)seq(sum(Ans=Ans(I)),I,1,dim(Ans→A
cumSum(Ans→B
SortD(∟A,∟B
cumSum(0≠ΔList(augment({0},∟A→A
SortA(∟B,∟A
∟A-1
```
# Explanation
```
seq(sum(Ans=Ans(I)),I,1,dim(Ans    Calculates the frequency of each element of Ans.
                                   Comparing a value to a list returns a list of booleans,
                                   so taking the sum will produce the number of matches.
Ans+max(Ans+1)                     Multiplies each frequency by one more than the max element,
                                   then adds each original value.
                                   This ensures that identical values with the same frequency
                                   will be grouped together when sorting.
                                   Additionally, all resulting values will be positive.
→A                                 Stores to ∟A.
cumSum(Ans→B                       Stores the prefix sum of the result into ∟B.
                                   Since ∟A has only positive values, ∟B is guaranteed
                                   to be strictly increasing.
SortD(∟A,∟B                        Sort ∟A in descending order (by frequency), grouping
                                   identical values together. Also, dependently sort ∟B
                                   so the original ordering can be restored.
       0≠ΔList(augment({0},∟A      Prepends a 0 to ∟A and compares each consecutive difference
                                   to 0. This places a 1 at each element that is different
                                   from the previous element, and 0 everywhere else.
                                   The first element is never 0, so it is considered different.
cumSum(                      →A    Takes the prefix sum of this list and stores to ∟A.
                                   Since there is a 1 at each element with a new value,
                                   the running sum will increase by 1 at each value change.
                                   As a result, we've created a unique mapping.
SortA(∟B,∟A                        Sorts ∟B in ascending order with ∟A as a dependent,
                                   restoring the original element ordering.
∟A-1                               Since we started counting up at 1 instead of 0,
                                   subtract 1 from each element in ∟A and return it.
```
[Answer]
# [Perl 5](https://www.perl.org/), 77 + 1 (-a) = 78 bytes
```
$c{$_}++for@F;%r=map{$_=>$i++.$"}sort{$c{$b}<=>$c{$a}}keys%c;print$r{$_}for@F
```
[Try it online!](https://tio.run/##HYzBCsIwEER/ZZH0FFq6amuktnjy5jdILBVCtQmbXErJr7smnubxmBk30bthFuMmHlHKl6XrrSuo/2iXTD8II2UldtFbCltuPeMl2QQ6xnlafTF2jswSBOWH/54ZARUcQUELeAbcA54yHiCHAoT2a10wdvFc3puqxppL/QM "Perl 5 – Try It Online")
[Answer]
# JavaScript (ES6), 91 bytes
Using a list of unique values, sorted by frequency.
```
x=>x.map(x=>Object.keys(C).sort((a,b)=>C[b]-C[a]).indexOf(x+''),C={},x.map(v=>C[v]=-~C[v]))
```
**Test**
```
var F=
x=>x.map(x=>Object.keys(C).sort((a,b)=>C[b]-C[a]).indexOf(x+''),C={},x.map(v=>C[v]=-~C[v]))
Test=`[1 2 1 4 5] -> [0 1 0 2 3]
[3 2 2 1 5 7 2] -> [1 0 0 2 3 4 0]
[8 8 8 8 8] -> [0 0 0 0 0]
[2] -> [0]
[8 6 8 4 6 8 2 4 6 8 0 2 4 6 8] -> [0 1 0 2 1 0 3 2 1 0 4 3 2 1 0]
[14 1] -> [1 0]
[19 6 4 9 14 17 10 9 6 14 8 14 6 15] -> [8 0 3 2 1 7 5 2 0 1 4 1 0 6]
[15] -> [0]
[1 18 4 8 6 19 12 17 6 13 7 6 8 1 6] -> [1 8 3 2 0 9 5 7 0 6 4 0 2 1 0]
[9 10 11 9 7 11 16 17 11 8 7] -> [2 4 0 2 1 0 5 6 0 3 1]
[1 3 16 19 14] -> [0 1 3 4 2]
[18 8] -> [1 0]
[13 4 9 6] -> [3 0 2 1]
[16 16 18 6 12 10 4 6] -> [1 1 5 0 4 3 2 0]
[11 18] -> [0 1]
[14 18 18 11 9 8 13 3 3 4] -> [7 1 1 5 4 3 6 0 0 2]
[20 19 1 1 13] -> [3 2 0 0 1]
[12] -> [0]
[1 14 20 4 18 15 19] -> [0 2 6 1 4 3 5]
[13 18 20] -> [0 1 2]
[9 1 12 2] -> [2 0 3 1]
[15 11 2 9 10 19 17 10 19 11 16 5 13 2] -> [7 2 0 5 1 3 9 1 3 2 8 4 6 0]
[5 4 2 2 19 14 18 11 3 12 20 14 2 19 7] -> [5 4 0 0 2 1 9 7 3 8 10 1 0 2 6]
[9 11 13 13 13 12 17 8 4] -> [3 4 0 0 0 5 6 2 1]
[10 14 16 17 7 4 3] -> [3 4 5 6 2 1 0]
[2 4 8 7 8 19 16 11 10 19 4 7 8] -> [4 1 0 2 0 3 7 6 5 3 1 2 0]
[15 17 20 18 20 13 6 10 4 19 9 15 18 17 5] -> [0 1 3 2 3 9 6 8 4 10 7 0 2 1 5]
[15 14 4 5 5 5 3 3 19 12 4] -> [5 4 2 0 0 0 1 1 6 3 2]
[7 12] -> [0 1]
[18 5 18 2 5 20 8 8] -> [2 0 2 3 0 4 1 1]
[4 6 10 7 3 1] -> [2 3 5 4 1 0]
[5] -> [0]
[6 12 14 18] -> [0 1 2 3]
[7 15 13 3 4 7 20] -> [0 4 3 1 2 0 5]
[10 15 19 14] -> [0 2 3 1]
[14] -> [0]
[19 10 20 12 17 3 6 16] -> [6 2 7 3 5 0 1 4]
[9 4 7 18 18 15 3] -> [4 2 3 0 0 5 1]
[7 4 13 7] -> [0 1 2 0]
[19 1 10 3 1] -> [3 0 2 1 0]
[8 14 20 4] -> [1 2 3 0]
[17 20 18 11 1 15 7 2] -> [5 7 6 3 0 4 2 1]
[11 4 3 17] -> [2 1 0 3]
[1 9 15 1 20 8 6] -> [0 3 4 0 5 2 1]
[16 13 10] -> [2 1 0]
[17 20 20 12 19 10 19 7 8 5 12 19] -> [7 2 2 1 0 6 0 4 5 3 1 0]
[18 11] -> [1 0]
[2 16 7 12 10 18 4 14 14 7 15 4 8 3 14] -> [3 9 2 7 6 10 1 0 0 2 8 1 5 4 0]
[5 7 2 2 16 14 7 7 18 19 16] -> [3 0 1 1 2 4 0 0 5 6 2]
[8 6 17 5 10 2 14] -> [3 2 6 1 4 0 5]`
Test.split(`\n`).forEach(row => {
  row=row.match(/\d+/g)
  var nv = row.length/2
  var tc = row.slice(0,nv)
  var exp = row.slice(nv)
  var xsum = eval(exp.join`+`)
  var result = F(tc)
  var rsum = eval(result.join`+`)
  var ok = xsum == rsum
  console.log('Test ' + (ok ? 'OK':'KO')
  + '\nInput [' + tc 
  + ']\nExpected (sum ' + xsum + ') ['+ exp 
  + ']\nResult (sum ' + rsum + ') [' + result + ']')
  
})
```
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 10 bytes
```
Qċ@Þ⁸UiⱮµ’
```
[Try it online!](https://tio.run/##y0rNyan8/z/wSLfD4XmPGneEZj7auO7Q1kcNM////x9tqKNgpKMAJE10FExjAQ "Jelly – Try It Online")
I'm certain there's a way to remove at least one byte, but I've spend an hour not finding it so...
## How it works
```
Qċ@Þ⁸UiⱮµ’ - Main link. Takes A on the left
Q          - Remove duplicates in A
   Þ       - Sort by the following function:
 ċ         -   Number of times...
  @ ⁸      -   ...in A
     U     - Reverse. Call this l
       Ɱ   - Over each element in A...
      i    -   Find its index in l
        µ’ - Decrement to account for Jelly's 1-indexing
```
[Answer]
# [PHP](https://php.net/), 92 bytes
```
$b=array_unique($a);print_r(array_map(function($v)use($b){return array_search($v,$b);},$a));
```
[Try it online!](https://tio.run/##JYzNCsIwEIRfpYccEtiDgfpTYvFBRMq2RJKDcd0mQik@e9zSyzAz3zAUqF5vFKhR2N9tBydooQPbgj2DPcBWSLhsIu74cFWNPTLjMpQUP8VrhcYRx5QH1jt4IelnSVOO76TV15RZVqNZ2efCqdlHs0eegmAQ5H4gN8bV@gc "PHP – Try It Online")
[Answer]
# [R](https://www.r-project.org/), 58 bytes
```
x=scan();cat(match(x,names(z<-table(x))[rev(order(z))])-1)
```
[Try it online!](https://tio.run/##HYhbCoAgEACvsp@7kND2huok0cdmQh9ZYBLi5U2CgWHGpRTmR8uFNGrxaMXrA0NxiTUPxkl52U6DgWhx5sXb7cZhJFpJMaUKuIMeOLsEHqAB/smrzTFAnSt9 "R – Try It Online")
Port of [Chas Brown's Python answer](https://codegolf.stackexchange.com/a/138759/67312).
`table` computes the counts of each element in `x` (storing the values as the `names` attribute), `order` returns a permutation of the indices in `z`, and `match` returns the index of the first match of `x` in `names(z)`. Then it subtracts `1` because R indices are 1-based.
]