#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
class Solution{
public:
    void nextPermutation(vector<int> &num) {
        if(num.size() == 0)
            return;

        const vector<int>::reverse_iterator rfirst= num.rbegin();
        const vector<int>::reverse_iterator rend = num.rend();

        auto pivot = next(rfirst);
        while(pivot != rend && *pivot >= *prev(pivot))
        {
            ++pivot;
        }
        
        if(pivot == rend)
        {
            reverse(rfirst,rend);
            return;
        }
        //find the first num great than pivot
        auto change = rfirst;
        while(*change<=*pivot)
            ++change;

        swap(*change,*pivot);
        reverse(rfirst,pivot);
        return;
    }
};

int main()
{
    vector<int> num;
    num.push_back(1);
    num.push_back(1);
    num.push_back(5);
     
    Solution myS;
    myS.nextPermutation(num);
    return 0;
}