using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using static System.Console;
 
BigInteger ithDuplicatedPermutationInv(int[] a)
{
    int N = a.Length;
    BigInteger i = 1, P = 1;
    var c = new SortedDictionary<int, int>();
 
    foreach (var (k, j) in a.Reverse().Select((k, j) => (k, j + 1))) {
        int n = c.ContainsKey(k) ? ++c[k] : c[k] = 1;
        int s = c.TakeWhile(x => x.Key < k).Sum(x => x.Value);
        i += P * s / n;
        P = P * j / n;
    }
 
    return i;
}
 
var Q = new[] {
    new[] {1, 2, 3, 4, 5, 6, 7, 8, 9},
    new[] {1, 2, 3, 4, 5, 6, 7, 9, 8},
    new[] {1, 2, 3, 4, 5, 6, 8, 7, 9},
    new[] {9, 8, 7, 6, 5, 4, 3, 2, 1},
    null,
    new[] {1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4},
    new[] {1, 1, 1, 2, 2, 2, 3, 3, 4, 3, 4, 4},
    new[] {1, 1, 1, 2, 2, 2, 3, 3, 4, 4, 3, 4},
    new[] {2, 2, 2, 3, 3, 1, 4, 3, 4, 1, 1, 4},
    new[] {3, 2, 4, 4, 2, 4, 3, 3, 1, 1, 1, 2},
    new[] {4, 4, 4, 3, 3, 3, 2, 2, 2, 1, 1, 1},
    null,
    new[] {1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5},
    new[] {1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 5, 4, 5, 5},
    new[] {1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 5, 5, 4, 5},
    new[] {1, 1, 1, 3, 3, 3, 4, 4, 2, 5, 4, 5, 2, 2, 5},
    new[] {1, 1, 1, 4, 3, 5, 5, 3, 5, 4, 4, 2, 2, 2, 3},
    new[] {1, 1, 1, 5, 5, 5, 4, 4, 4, 3, 3, 3, 2, 2, 2},
    new[] {5, 5, 5, 4, 4, 4, 3, 3, 3, 2, 2, 2, 1, 1, 1},
    null,
    new[] {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},
    new[] {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},
    new[] {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},
    new[] {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},
    new[] {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},
    new[] {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,
    new[] {3, 1, 4, 1, 5, 9}
};
 
foreach (var q in Q) {
    if (q != null) {
        WriteLine($"入力: [{string.Join(", ", q)}]");
        WriteLine($"出力: {ithDuplicatedPermutationInv(q)}");
    }
    WriteLine();
}

dXNpbmcgU3lzdGVtLkNvbGxlY3Rpb25zLkdlbmVyaWM7CnVzaW5nIFN5c3RlbS5MaW5xOwp1c2luZyBTeXN0ZW0uTnVtZXJpY3M7CnVzaW5nIHN0YXRpYyBTeXN0ZW0uQ29uc29sZTsKCkJpZ0ludGVnZXIgaXRoRHVwbGljYXRlZFBlcm11dGF0aW9uSW52KGludFtdIGEpCnsKICAgIGludCBOID0gYS5MZW5ndGg7CiAgICBCaWdJbnRlZ2VyIGkgPSAxLCBQID0gMTsKICAgIHZhciBjID0gbmV3IFNvcnRlZERpY3Rpb25hcnk8aW50LCBpbnQ+KCk7CgogICAgZm9yZWFjaCAodmFyIChrLCBqKSBpbiBhLlJldmVyc2UoKS5TZWxlY3QoKGssIGopID0+IChrLCBqICsgMSkpKSB7CiAgICAgICAgaW50IG4gPSBjLkNvbnRhaW5zS2V5KGspID8gKytjW2tdIDogY1trXSA9IDE7CiAgICAgICAgaW50IHMgPSBjLlRha2VXaGlsZSh4ID0+IHguS2V5IDwgaykuU3VtKHggPT4geC5WYWx1ZSk7CiAgICAgICAgaSArPSBQICogcyAvIG47CiAgICAgICAgUCA9IFAgKiBqIC8gbjsKICAgIH0KCiAgICByZXR1cm4gaTsKfQoKdmFyIFEgPSBuZXdbXSB7CiAgICBuZXdbXSB7MSwgMiwgMywgNCwgNSwgNiwgNywgOCwgOX0sCiAgICBuZXdbXSB7MSwgMiwgMywgNCwgNSwgNiwgNywgOSwgOH0sCiAgICBuZXdbXSB7MSwgMiwgMywgNCwgNSwgNiwgOCwgNywgOX0sCiAgICBuZXdbXSB7OSwgOCwgNywgNiwgNSwgNCwgMywgMiwgMX0sCiAgICBudWxsLAogICAgbmV3W10gezEsIDEsIDEsIDIsIDIsIDIsIDMsIDMsIDMsIDQsIDQsIDR9LAogICAgbmV3W10gezEsIDEsIDEsIDIsIDIsIDIsIDMsIDMsIDQsIDMsIDQsIDR9LAogICAgbmV3W10gezEsIDEsIDEsIDIsIDIsIDIsIDMsIDMsIDQsIDQsIDMsIDR9LAogICAgbmV3W10gezIsIDIsIDIsIDMsIDMsIDEsIDQsIDMsIDQsIDEsIDEsIDR9LAogICAgbmV3W10gezMsIDIsIDQsIDQsIDIsIDQsIDMsIDMsIDEsIDEsIDEsIDJ9LAogICAgbmV3W10gezQsIDQsIDQsIDMsIDMsIDMsIDIsIDIsIDIsIDEsIDEsIDF9LAogICAgbnVsbCwKICAgIG5ld1tdIHsxLCAxLCAxLCAyLCAyLCAyLCAzLCAzLCAzLCA0LCA0LCA0LCA1LCA1LCA1fSwKICAgIG5ld1tdIHsxLCAxLCAxLCAyLCAyLCAyLCAzLCAzLCAzLCA0LCA0LCA1LCA0LCA1LCA1fSwKICAgIG5ld1tdIHsxLCAxLCAxLCAyLCAyLCAyLCAzLCAzLCAzLCA0LCA0LCA1LCA1LCA0LCA1fSwKICAgIG5ld1tdIHsxLCAxLCAxLCAzLCAzLCAzLCA0LCA0LCAyLCA1LCA0LCA1LCAyLCAyLCA1fSwKICAgIG5ld1tdIHsxLCAxLCAxLCA0LCAzLCA1LCA1LCAzLCA1LCA0LCA0LCAyLCAyLCAyLCAzfSwKICAgIG5ld1tdIHsxLCAxLCAxLCA1LCA1LCA1LCA0LCA0LCA0LCAzLCAzLCAzLCAyLCAyLCAyfSwKICAgIG5ld1tdIHs1LCA1LCA1LCA0LCA0LCA0LCAzLCAzLCAzLCAyLCAyLCAyLCAxLCAxLCAxfSwKICAgIG51bGwsCiAgICBuZXdbXSB7MSwgMSwgMSwgMSwgMSwgMiwgMiwgMiwgMiwgMiwgMywgMywgMywgMywgMywgNCwgNCwgNCwgNCwgNCwgNSwgNSwgNSwgNSwgNSwgCiAgICAgNiwgNiwgNiwgNiwgNiwgNywgNywgNywgNywgNywgOCwgOCwgOCwgOCwgOCwgOSwgOSwgOSwgOSwgOSwgMTAsIDEwLCAxMCwgMTAsIDEwfSwKICAgIG5ld1tdIHsxLCAxLCAxLCAxLCAxLCAyLCAyLCAyLCAyLCAyLCAzLCAzLCAzLCAzLCAzLCA0LCA0LCA0LCA0LCA0LCA1LCA1LCA1LCA1LCA1LAogICAgIDYsIDYsIDYsIDYsIDYsIDcsIDcsIDcsIDcsIDcsIDgsIDgsIDgsIDgsIDgsIDksIDksIDksIDksIDEwLCA5LCAxMCwgMTAsIDEwLCAxMH0sCiAgICBuZXdbXSB7MSwgMSwgMSwgMSwgMSwgMiwgMiwgMiwgMiwgMiwgMywgMywgMywgMywgMywgNCwgNCwgNCwgNCwgNCwgNSwgNSwgNSwgNSwgNSwKICAgICA2LCA2LCA2LCA2LCA2LCA3LCA3LCA3LCA3LCA3LCA4LCA4LCA4LCA4LCA4LCA5LCA5LCA5LCA5LCAxMCwgMTAsIDksIDEwLCAxMCwgMTB9LAogICAgbmV3W10gezEsIDEsIDEsIDEsIDEsIDIsIDIsIDIsIDIsIDIsIDMsIDMsIDMsIDMsIDMsIDQsIDQsIDQsIDQsIDQsIDUsIDUsIDUsIDUsIDUsCiAgICAgNiwgNiwgNiwgNiwgNiwgNywgNywgNywgNywgNywgOCwgOSwgOSwgMTAsIDEwLCA4LCA4LCA5LCA4LCA4LCA5LCAxMCwgMTAsIDEwLCA5fSwKICAgIG5ld1tdIHsxLCAxLCAxLCAxLCAxLCAyLCAyLCAyLCAyLCAyLCAzLCAzLCAzLCAzLCAzLCA0LCA0LCA0LCA0LCA0LCA1LCA1LCA1LCA1LCA1LAogICAgIDYsIDYsIDYsIDYsIDYsIDcsIDcsIDcsIDcsIDcsIDgsIDEwLCAxMCwgOSwgOCwgOCwgOSwgMTAsIDEwLCA4LCA5LCAxMCwgOSwgOCwgOX0sCiAgICBuZXdbXSB7MTAsIDEwLCAxMCwgMTAsIDEwLCA5LCA5LCA5LCA5LCA5LCA4LCA4LCA4LCA4LCA4LCA3LCA3LCA3LCA3LCA3LCA2LCA2LCA2LCA2LCA2LAogICAgIDUsIDUsIDUsIDUsIDUsIDQsIDQsIDQsIDQsIDQsIDMsIDMsIDMsIDMsIDMsIDIsIDIsIDIsIDIsIDIsIDEsIDEsIDEsIDEsIDF9LAogICAgbnVsbCwKICAgIG5ld1tdIHszLCAxLCA0LCAxLCA1LCA5fQp9OwoKZm9yZWFjaCAodmFyIHEgaW4gUSkgewogICAgaWYgKHEgIT0gbnVsbCkgewogICAgICAgIFdyaXRlTGluZSgkIuWFpeWKmzogW3tzdHJpbmcuSm9pbigiLCAiLCBxKX1dIik7CiAgICAgICAgV3JpdGVMaW5lKCQi5Ye65YqbOiB7aXRoRHVwbGljYXRlZFBlcm11dGF0aW9uSW52KHEpfSIpOwogICAgfQogICAgV3JpdGVMaW5lKCk7Cn0=