Given two positive integers N and K, the task is to find a permutation P of length N such that the sum of every adjacent pair of elements in P is greater than or equal to K. If there are multiple permutations that satisfy the condition, you should output the lexicographically smallest one. If there is no permutation that satisfies the condition, you should output -1.

Note: In other words, you need to find a permutation P of the numbers [1, 2, …, N] such that P[i] + P[i+1] ≥ K for all 1 ≤ i ≤ N-1. The lexicographically smallest permutation is the one that comes first in alphabetical order when the numbers are written out in sequence. For example, [1, 2, 3] is lexicographically smaller than [1, 3, 2].

Examples:

Input: N = 6, K = 5
Output: 1 4 2 3 5 6
Explanation: Considering the permutation 1 4 2 3 5 6 sum of adjacent elements is greater than 5. There exists different permutation such as [3, 5, 1, 4, 2, 6], [1, 5, 2, 3, 4, 6], [6, 1, 4, 3, 5, 6]etc. But 
[1, 4, 2, 3, 5, 6] is the lexicographically smallest one among them.

Input: N = 4, K = 6
Output: -1
Explanation: No such permutation exists which satisfies the above condition.

Approach: To solve the problem follow the below idea:

The idea is to first store K-1 numbers, starting with K, in descending order, at even indices of the array, and then store the remaining numbers in ascending order at odd indices of the array. Finally, any remaining indices are filled with the natural sequence of numbers.

Below are the steps for the above approach:

• Check if N is less than K. If so then no permutation can be generated which satisfies the above condition so print -1 and return.
• Create a vector say a to store the answer.
• Initialize two variables x = –K and y = 2.
• Increment k to the original value.
• Run a loop from i = 0 to i ≤ N,
  • Check if i > 1 and i < K,
    • Check if i%2 == 0, add the value x to the resultant vector a, and decrement x by 1.
    • Else, add the value y to the resultant vector a, and increment y by 1.
  • Else, add i to the resultant vector.

// C++ Program for the above approach
#include <bits/stdc++.h>
using namespace std;

void Generatepermutation(int n, int k)
{

    // Check if n is less than k. If so
    // then no permutation can be generated
    // which satisfies above condition so
    // print -1 and return.
    if (n < k - 1) {
        cout << -1 << endl;
        return;
    }

    // Create a vector to store the answer
    vector<int> a;

    // Store k-1 number to store values in
    // descending order in even indices
    int x = --k;

    // Start with 2 to store values in
    // ascending order in odd indices
    int y = 2;

    // Increment k to orignal value
    k++;

    // Iterate till n
    for (int i = 1; i <= n; i++) {

        // To store values in the
        // range from 2 to k-1
        if (i > 1 && i < k) {

            // Store values in even
            // indices of array
            if (i % 2 == 0) {
                a.push_back(x);
                x--;
            }

            else {
                a.push_back(y);
                y++;
            }
        }
        else {

            // Store values according to
            // natural sequence in array
            a.push_back(i);
        }
    }

    // Print the permutation generated
    for (int i = 0; i < a.size(); i++) {
        cout << a[i] << " ";
    }
    cout << endl;
}

// Drivers code
int main()
{
    int N = 6, K = 5;

    // Function call
    Generatepermutation(N, K);

    return 0;
}

Time Complexity: O(N)
Auxiliary Space: O(N)