Easy to Understand || C++ runtime : 0 ms 
IntuitionApproachIn recursion fun, if odd==1 then at ith position it tries to fit any odd number which is not taken as far, checked by liya vector. If odd==0 th
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->

# Approach
<!-- Describe your approach to solving the problem. -->
In recursion fun, if odd==1 then at ith position it tries to fit any odd number which is not taken as far, checked by liya vector. If odd==0 then even and if odd ==-1 (or else portion) : it tries to fit any number from 1 to n in ascending order.
Now if n is odd then permutation will surely starts from odd number but for even it could start from both even and odd.
As k is upto 1e15 so we need to calculate fact upto 17, above which it will surely be able to make a permutation.

# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```cpp []
# define ll long long
class Solution {
public:

    ll fact[19];
    bool fun(ll k,int n,int i,int odd, vector<ll>& ans, vector<ll> &liya, int od, int ev){
        if(i>n)return true;
        if(odd==1){
            int bod=od-1,bev=ev;
            for(int j=1;j<=n;j+=2){
                if(liya[j]==0){
                    if(bod>=17 || bev>=17 || fact[bod]*(long double)fact[bev]>=k){
                        liya[j]=1;
                        ans[i]=j;
                        return fun(k, n, i+1, 0, ans, liya, bod, bev);
                    }else{
                        k-=fact[bod]*fact[bev];
                    }
                }
            }
            return false;
        }else if(odd==0){
            int bod=od,bev=ev-1;
            for(int j=2;j<=n;j+=2){
                if(liya[j]==0){
                    if(bod>=17 || bev>=17 || fact[bod]*(long double)fact[bev]>=k){
                        liya[j]=1;
                        ans[i]=j;
                        return fun(k, n, i+1, 1, ans, liya, bod, bev);
                    }else{
                        k-=fact[bod]*fact[bev];
                    }
                }
            }
            return false;
        }else{
            for(int j=1;j<=n;j++){
                if(liya[j]==0){
                    int bod=od,bev=ev;
                    if(j&1){
                        bod--;
                    }else{
                        bev--;
                    }
                    if(bod>=17 || bev>=17 || fact[bod]*(long double)fact[bev]>=k){
                        liya[j]=1;
                        ans[i]=j;
                        return fun(k, n, i+1, (j&1)^1 , ans, liya, bod, bev);
                    }else{
                        k-=fact[bod]*fact[bev];
                    }
                }
            }
            return false;
        }
    }


    vector<int> permute(int n, long long k) {
        int ev=n/2;
        int od=n-ev;
        fact[0]=1;
        for(ll i=1;i<19;i++){
            fact[i]=fact[i-1]*i;
        }
        vector<ll> ans(n+1,0);
        vector<ll> liya(n+1,0);

        bool re1= fun(k, n, 1, 1, ans, liya, od, ev);
        vector<ll> arr1;
        arr1=ans;

        ans.assign(n+1,0);
        liya.assign(n+1,0);
        bool re2=false;
        if(!(n&1)){
            re2= fun(k, n, 1, -1, ans, liya, od, ev);
        }
        
        vector<int> bhejo;
        if(re1 && re2){
            if(arr1[1]<ans[1]){
                for(int j=1;j<=n;j++){
                    bhejo.push_back(arr1[j]);
                }
            }else{
                for(int j=1;j<=n;j++){
                    bhejo.push_back(ans[j]);
                }
            }
        }else if(re1){
            for(int j=1;j<=n;j++){
                bhejo.push_back(arr1[j]);
            }
        }else if(re2){
            for(int j=1;j<=n;j++){
                bhejo.push_back(ans[j]);
            }
        }else{
            return vector<int>(0);
        }
        return bhejo;




    }
};
```
['C++']