B. Shoe Shuffling

A class of students got bored wearing the same pair of shoes every day, so they decided to shuffle their shoes among themselves. In this problem, a pair of shoes is inseparable and is considered as a single object. There are 𝑛 students in the class, and you are given an array 𝑠 in non-decreasing order, where 𝑠𝑖 is the shoe size of the 𝑖 -th student. A shuffling of shoes is valid only if no student gets their own shoes and if every student gets shoes of size greater than or equal to their size.

time limit per test: 1 second | memory limit per test: 256 megabytes

There are n students in the class, and you are given an array s in non-decreasing order, where s_i is the shoe size of the i-th student. A shuffling of shoes is valid only if no student gets their own shoes and if every student gets shoes of size greater than or equal to their size.

You have to output a permutation p of {1, 2, …, n} denoting a valid shuffling of shoes, where the i-th student gets the shoes of the p_i-th student (p_i ≠ i). And output −1 if a valid shuffling does not exist.

A permutation is an array consisting of n distinct integers from 1 to n in arbitrary order. For example, [2, 3, 1, 5, 4] is a permutation, but [1, 2, 2] is not a permutation (2 appears twice in the array) and [1, 3, 4] is also not a permutation (n = 3 but there is 4 in the array).

Input

Each test contains multiple test cases. The first line contains a single integer t (1 ≤ t ≤ 1000) — the number of test cases. Description of the test cases follows.

The first line of each test case contains a single integer n (1 ≤ n ≤ 10⁵) — the number of students.

The second line of each test case contains n integers s₁, s₂, …, s_n (1 ≤ s_i ≤ 10⁹, and for all 1 ≤ i < n, s_i ≤ s_i+1) — the shoe sizes of the students.

It is guaranteed that the sum of n over all test cases does not exceed 10⁵.

Output

For each test case, print the answer in a single line using the following format.

If a valid shuffling does not exist, print the number −1 as the answer.

If a valid shuffling exists, print n space-separated integers — a permutation p of 1, 2, …, n denoting a valid shuffling of shoes where the i-th student gets the shoes of the p_i-th student. If there are multiple answers, then print any of them.

Example

Input

2
5
1 1 1 1 1
6
3 6 8 13 15 21

Output

5 1 2 3 4
-1

Note

In the first test case, any permutation p of 1, …, n where p_i ≠ i would represent a valid shuffling since all students have equal shoe sizes, and thus anyone can wear anyone’s shoes.

In the second test case, it can be shown that no valid shuffling is possible.

void solve()
{

    int n;
    cin >> n;

    vi v(n);
    for (int i = 0; i < n; i++)
    {
        cin >> v[i];
    }

    if (n == 1)
    {
        cout << -1 << endl;
        return;
    }

    int i = 0;

    while (i < n)
    {
        int j = i;
        while (i < n && j < n && v[i] == v[j])
            j++;
        if (j - i == 1)
        {
            cout << -1 << endl;
            return;
        }
        i = j;
    }

    i = 0;

    while (i < n)
    {
        int j = i;
        while (i < n && j < n && v[i] == v[j])
            j++;
        for (int k = i + 1; k < j; k++)
            cout << k + 1 << " ";
        cout << i + 1 << " ";
        i = j;
    }

    cout << endl;
}


#include <bits/stdc++.h>

using namespace std;

#define int long long int
#define F first
#define S second
#define pb push_back
#define si set<int>
#define vi vector<int>
#define pii pair<int, int>
#define vpi vector<pii>
#define vpp vector<pair<int, pii>>
#define mii map<int, int>
#define mpi map<pii, int>
#define spi set<pii>
#define endl "\n"
#define sz(x) ((int)x.size())
#define all(p) p.begin(), p.end()
#define double long double
#define que_max priority_queue<int>
#define que_min priority_queue<int, vi, greater<int>>
#define bug(...) __f(#__VA_ARGS__, __VA_ARGS__)
#define print(a)          \
    for (auto x : a)      \
        cout << x << " "; \
    cout << endl
#define print1(a)    \
    for (auto x : a) \
    cout << x.F << " " << x.S << endl
#define print2(a, x, y)         \
    for (int i = x; i < y; i++) \
        cout << a[i] << " ";    \
    cout << endl
#define scanit(a, n)                             \
    for (ll indexaa = 0; indexaa < n; indexaa++) \
        cin >> a[indexaa];

inline int power(int a, int b)
{
    int x = 1;
    while (b)
    {
        if (b & 1)
            x *= a;
        a *= a;
        b >>= 1;
    }
    return x;
}

template <typename Arg1>
void __f(const char *name, Arg1 &&arg1) { cout << name << " : " << arg1 << endl; }
template <typename Arg1, typename... Args>
void __f(const char *names, Arg1 &&arg1, Args &&...args)
{
    const char *comma = strchr(names + 1, ',');
    cout.write(names, comma - names) << " : " << arg1 << " | ";
    __f(comma + 1, args...);
}

const int N = 200005;

void solve()
{

    int n;
    cin >> n;

    vi v(n);
    for (int i = 0; i < n; i++)
    {
        cin >> v[i];
    }

    if (n == 1)
    {
        cout << -1 << endl;
        return;
    }

    int i = 0;

    while (i < n)
    {
        int j = i;
        while (i < n && j < n && v[i] == v[j])
            j++;
        if (j - i == 1)
        {
            cout << -1 << endl;
            return;
        }
        i = j;
    }

    i = 0;

    while (i < n)
    {
        int j = i;
        while (i < n && j < n && v[i] == v[j])
            j++;
        for (int k = i + 1; k < j; k++)
            cout << k + 1 << " ";
        cout << i + 1 << " ";
        i = j;
    }

    cout << endl;
}

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    clock_t z = clock();

    int t = 1;
    cin >> t;
    while (t--)
        solve();

    return 0;
}

TagsB. Shoe ShufflingCodeforcesCodeCraft-22 and Codeforces Round 795 (Div. 2)

Raunit Verma

Technical Writer at CodingKaro

Share this on