An algorithm for obtaining the next permutation of the set of numbers was invented by Indian mathematician Pandit Narayana more than 600 years ago. Given array $$$a$$$. The way the next permutation is found with Narayana's algorithm: 1. Find the longest non-decreasing suffix (NDS). Let in starts in position $$$k$$$. 2. Swap $$$a_{k-1}$$$ and next largest number that exists in suffix $$$k$$$. 3. Reverse suffix $$$k$$$.

how find a tail

The Code

struct node {
    int val, heap_val, size; //size of this tree
    node* l,r; //left and right subtrees
    bool reversed, non_incr, non_decr;
    node(int Val) : val(Val), l(0), r(0), reversed(0), non_incr(0), non_decr(0) {
        heap_val = rand() * (1<<15) + rand(); //now heap_val to 2^30
    }
};
typedef node* treap;
treap root;

void next_p(int l, int r, treap t=root){
    treap lt,rt, swap1,swap2, t2;
    split(t,t,rt,r+1);
    int tail = tail(t);
    if(tail==l){
        t->reversed^=1; //just reverse it
        merge(t,t,rt); return;
    }
    l=tail; //elements to the left aren't changed
    split(t,lt,t,l-1); split(t,swap1,t,l); //separate p_(n-k)
    t->reversed^=1; //it's easier to reverse tail k before finding p_next
    int p_next = upper_b(l,r,t); //find p_next by binary search
    split(t,t2,t,p_next); split(t,swap2,t,p_next+1); //separate p_next
    merge(t,swap1,t); merge(t,t2,t); merge(t,swap2,t); //unite tail k+1
    merge(t,lt,t); merge(t,t,rt); //unite all
}