library(gmp)
 
printf <- function(...) cat(sprintf(...))
 
ithDuplicatedPermutationInv <- function(a)
{
    N <- length(a)
    i <- P <- as.bigz(1)
 
    a <- as.integer(factor(a))
    c <- table(a); c[] <- 0L
 
    for (j in N:1) {
        k <- a[j]
        c[k] <- c[k] + 1L
        i <- i + (P * sum(c[0:(k - 1)])) %/% c[k]
        P <- (P * (N - j + 1)) %/% c[k]
    }
 
    i
}
 
Q <- list(
    c(1, 2, 3, 4, 5, 6, 7, 8, 9),
    c(1, 2, 3, 4, 5, 6, 7, 9, 8),
    c(1, 2, 3, 4, 5, 6, 8, 7, 9),
    c(9, 8, 7, 6, 5, 4, 3, 2, 1),
    NULL,
    c(1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4),
    c(1, 1, 1, 2, 2, 2, 3, 3, 4, 3, 4, 4),
    c(1, 1, 1, 2, 2, 2, 3, 3, 4, 4, 3, 4),
    c(2, 2, 2, 3, 3, 1, 4, 3, 4, 1, 1, 4),
    c(3, 2, 4, 4, 2, 4, 3, 3, 1, 1, 1, 2),
    c(4, 4, 4, 3, 3, 3, 2, 2, 2, 1, 1, 1),
    NULL,
    c(1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5),
    c(1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 5, 4, 5, 5),
    c(1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 5, 5, 4, 5),
    c(1, 1, 1, 3, 3, 3, 4, 4, 2, 5, 4, 5, 2, 2, 5),
    c(1, 1, 1, 4, 3, 5, 5, 3, 5, 4, 4, 2, 2, 2, 3),
    c(1, 1, 1, 5, 5, 5, 4, 4, 4, 3, 3, 3, 2, 2, 2),
    c(5, 5, 5, 4, 4, 4, 3, 3, 3, 2, 2, 2, 1, 1, 1),
    NULL,
    c(1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 
      6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10),
    c(1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5,
      6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 9, 9, 9, 9, 10, 9, 10, 10, 10, 10),
    c(1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5,
      6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 9, 9, 9, 9, 10, 10, 9, 10, 10, 10),
    c(1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5,
      6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 8, 9, 9, 10, 10, 8, 8, 9, 8, 8, 9, 10, 10, 10, 9),
    c(1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5,
      6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 8, 10, 10, 9, 8, 8, 9, 10, 10, 8, 9, 10, 9, 8, 9),
    c(10, 10, 10, 10, 10, 9, 9, 9, 9, 9, 8, 8, 8, 8, 8, 7, 7, 7, 7, 7, 6, 6, 6, 6, 6,
      5, 5, 5, 5, 5, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1),
    NULL,
    c(3, 1, 4, 1, 5, 9)
)
 
for (q in Q) {
    if (length(q)) {
        printf("入力: [%s]\n", toString(q))
        printf("出力: %s\n", format(ithDuplicatedPermutationInv(q)))
    }
    printf("\n")
}

bGlicmFyeShnbXApCgpwcmludGYgPC0gZnVuY3Rpb24oLi4uKSBjYXQoc3ByaW50ZiguLi4pKQoKaXRoRHVwbGljYXRlZFBlcm11dGF0aW9uSW52IDwtIGZ1bmN0aW9uKGEpCnsKICAgIE4gPC0gbGVuZ3RoKGEpCiAgICBpIDwtIFAgPC0gYXMuYmlneigxKQoKICAgIGEgPC0gYXMuaW50ZWdlcihmYWN0b3IoYSkpCiAgICBjIDwtIHRhYmxlKGEpOyBjW10gPC0gMEwKCiAgICBmb3IgKGogaW4gTjoxKSB7CiAgICAgICAgayA8LSBhW2pdCiAgICAgICAgY1trXSA8LSBjW2tdICsgMUwKICAgICAgICBpIDwtIGkgKyAoUCAqIHN1bShjWzA6KGsgLSAxKV0pKSAlLyUgY1trXQogICAgICAgIFAgPC0gKFAgKiAoTiAtIGogKyAxKSkgJS8lIGNba10KICAgIH0KCiAgICBpCn0KClEgPC0gbGlzdCgKICAgIGMoMSwgMiwgMywgNCwgNSwgNiwgNywgOCwgOSksCiAgICBjKDEsIDIsIDMsIDQsIDUsIDYsIDcsIDksIDgpLAogICAgYygxLCAyLCAzLCA0LCA1LCA2LCA4LCA3LCA5KSwKICAgIGMoOSwgOCwgNywgNiwgNSwgNCwgMywgMiwgMSksCiAgICBOVUxMLAogICAgYygxLCAxLCAxLCAyLCAyLCAyLCAzLCAzLCAzLCA0LCA0LCA0KSwKICAgIGMoMSwgMSwgMSwgMiwgMiwgMiwgMywgMywgNCwgMywgNCwgNCksCiAgICBjKDEsIDEsIDEsIDIsIDIsIDIsIDMsIDMsIDQsIDQsIDMsIDQpLAogICAgYygyLCAyLCAyLCAzLCAzLCAxLCA0LCAzLCA0LCAxLCAxLCA0KSwKICAgIGMoMywgMiwgNCwgNCwgMiwgNCwgMywgMywgMSwgMSwgMSwgMiksCiAgICBjKDQsIDQsIDQsIDMsIDMsIDMsIDIsIDIsIDIsIDEsIDEsIDEpLAogICAgTlVMTCwKICAgIGMoMSwgMSwgMSwgMiwgMiwgMiwgMywgMywgMywgNCwgNCwgNCwgNSwgNSwgNSksCiAgICBjKDEsIDEsIDEsIDIsIDIsIDIsIDMsIDMsIDMsIDQsIDQsIDUsIDQsIDUsIDUpLAogICAgYygxLCAxLCAxLCAyLCAyLCAyLCAzLCAzLCAzLCA0LCA0LCA1LCA1LCA0LCA1KSwKICAgIGMoMSwgMSwgMSwgMywgMywgMywgNCwgNCwgMiwgNSwgNCwgNSwgMiwgMiwgNSksCiAgICBjKDEsIDEsIDEsIDQsIDMsIDUsIDUsIDMsIDUsIDQsIDQsIDIsIDIsIDIsIDMpLAogICAgYygxLCAxLCAxLCA1LCA1LCA1LCA0LCA0LCA0LCAzLCAzLCAzLCAyLCAyLCAyKSwKICAgIGMoNSwgNSwgNSwgNCwgNCwgNCwgMywgMywgMywgMiwgMiwgMiwgMSwgMSwgMSksCiAgICBOVUxMLAogICAgYygxLCAxLCAxLCAxLCAxLCAyLCAyLCAyLCAyLCAyLCAzLCAzLCAzLCAzLCAzLCA0LCA0LCA0LCA0LCA0LCA1LCA1LCA1LCA1LCA1LCAKICAgICAgNiwgNiwgNiwgNiwgNiwgNywgNywgNywgNywgNywgOCwgOCwgOCwgOCwgOCwgOSwgOSwgOSwgOSwgOSwgMTAsIDEwLCAxMCwgMTAsIDEwKSwKICAgIGMoMSwgMSwgMSwgMSwgMSwgMiwgMiwgMiwgMiwgMiwgMywgMywgMywgMywgMywgNCwgNCwgNCwgNCwgNCwgNSwgNSwgNSwgNSwgNSwKICAgICAgNiwgNiwgNiwgNiwgNiwgNywgNywgNywgNywgNywgOCwgOCwgOCwgOCwgOCwgOSwgOSwgOSwgOSwgMTAsIDksIDEwLCAxMCwgMTAsIDEwKSwKICAgIGMoMSwgMSwgMSwgMSwgMSwgMiwgMiwgMiwgMiwgMiwgMywgMywgMywgMywgMywgNCwgNCwgNCwgNCwgNCwgNSwgNSwgNSwgNSwgNSwKICAgICAgNiwgNiwgNiwgNiwgNiwgNywgNywgNywgNywgNywgOCwgOCwgOCwgOCwgOCwgOSwgOSwgOSwgOSwgMTAsIDEwLCA5LCAxMCwgMTAsIDEwKSwKICAgIGMoMSwgMSwgMSwgMSwgMSwgMiwgMiwgMiwgMiwgMiwgMywgMywgMywgMywgMywgNCwgNCwgNCwgNCwgNCwgNSwgNSwgNSwgNSwgNSwKICAgICAgNiwgNiwgNiwgNiwgNiwgNywgNywgNywgNywgNywgOCwgOSwgOSwgMTAsIDEwLCA4LCA4LCA5LCA4LCA4LCA5LCAxMCwgMTAsIDEwLCA5KSwKICAgIGMoMSwgMSwgMSwgMSwgMSwgMiwgMiwgMiwgMiwgMiwgMywgMywgMywgMywgMywgNCwgNCwgNCwgNCwgNCwgNSwgNSwgNSwgNSwgNSwKICAgICAgNiwgNiwgNiwgNiwgNiwgNywgNywgNywgNywgNywgOCwgMTAsIDEwLCA5LCA4LCA4LCA5LCAxMCwgMTAsIDgsIDksIDEwLCA5LCA4LCA5KSwKICAgIGMoMTAsIDEwLCAxMCwgMTAsIDEwLCA5LCA5LCA5LCA5LCA5LCA4LCA4LCA4LCA4LCA4LCA3LCA3LCA3LCA3LCA3LCA2LCA2LCA2LCA2LCA2LAogICAgICA1LCA1LCA1LCA1LCA1LCA0LCA0LCA0LCA0LCA0LCAzLCAzLCAzLCAzLCAzLCAyLCAyLCAyLCAyLCAyLCAxLCAxLCAxLCAxLCAxKSwKICAgIE5VTEwsCiAgICBjKDMsIDEsIDQsIDEsIDUsIDkpCikKCmZvciAocSBpbiBRKSB7CiAgICBpZiAobGVuZ3RoKHEpKSB7CiAgICAgICAgcHJpbnRmKCLlhaXlips6IFslc11cbiIsIHRvU3RyaW5nKHEpKQogICAgICAgIHByaW50Zigi5Ye65YqbOiAlc1xuIiwgZm9ybWF0KGl0aER1cGxpY2F0ZWRQZXJtdXRhdGlvbkludihxKSkpCiAgICB9CiAgICBwcmludGYoIlxuIikKfQ==