7.5 The Sorcerers’ Number Gauntlet
In the magical land of Numeria, two rival sorcerers - Gorath the Mighty and Monko the Cunning - discovered an ancient scroll containing three enchanted numbers: n, m, and k (with m<k). The scroll challenges them to arrange the numbers from 1 to n into a mystical sequence called a Number Gauntlet.
Each sorcerer has a magical lens to measure the power of the Gauntlet as it is being constructed, one number at a time (called prefixes):
Gorath’s Lens (f(i)): sums all numbers in the first i elements that are at least k, representing the surging power of the gauntlet.
Monko’s Lens (g(i)): sums all numbers in the first i elements that are at most m, representing the draining influence of the gauntlet.
The sorcerers’ goal is to maximize the difference between Gorath’s magical power and
Monko’s draining influence:
Total = (Σ from i=1 to n of f(i)) − (Σ from i=1 to n of g(i))
Your task is to conjure a mystical sequence (permutation) of numbers from 1 to n (each number exactly once) that produces the largest possible Total.
Note: While there may be multiple valid permutations, only a single permutation will be accepted where larger numbers are placed as early as possible in the permutation wherever feasible.
† A permutation of length n is an array consisting of n distinct integers from 1 to n in any order. For example, [2,3,1,5,4] is a permutation, but [1,2,2] is not a permutation (as 2 appears twice in the array) and [1,3,4] is also not a permutation (as n=3, but 4 appears in the array).
Constraints
1≤t≤10^4 - number of test cases.
For each test case:
2≤n≤10^5 - length of the sequence.
1≤m<k≤n - magical thresholds.
Sum of n over all test cases does not exceed 2⋅10^5
Input Format
The first line contains a single integer t - the number of test cases.
Each of the next t lines contains three integers n, m, and k for the corresponding test case.
Output Format
For each test case, print a permutation of length n - a sequence that satisfies the conditions of the problem.
Example 1
Input:
3
5 2 5
3 1 3
10 3 8
Output:
5 3 4 1 2
3 2 1
10 9 8 4 7 5 6 1 2 3
Explanation:
Test case 1: With permutation [5,3,4,1,2], the Total difference is maximized:
∑f(i)−∑g(i)=25−4=21
Log In to solve the Question