Solutions online use stl next_permutation but I don't want to use it.

Ive tried traversing from the back and finding element that is smaller than the greatest element among all elements to its right and swapping this smaller element with element that is just greater than it from the elements to its right and printing other right elements in sorted order. It shows WA in SPOJ.

problem: https://www.spoj.com/problems/JNEXT/

#include<bits/stdc++.h>
using namespace std;
int main(){
  long long t;
  cin >> t;
  while(t--){
    long long n;
    cin >> n;
    long long a[n]={0};
    for(int i=0;i<n;i++){
      cin >> a[i];
    }
    long long elem_max = a[n-1], smallest=0, index, ind, not_possible=0;
    vector<long long> sol;
    sol.push_back(elem_max);

    for(int i=n-2;i>=0;i--){
      if(a[i] < elem_max){
        sol.push_back(a[i]);
        smallest=a[i];
        index=i;
        break;
      }
      else{
        if(elem_max<a[i]){
          elem_max=a[i];
        }
        sol.push_back(a[i]);
      }
      if(i==0)not_possible=1;
    }
    if(not_possible || n==1){
      cout << -1 << endl;
    }
    else{
      for(int i=0;i<index;i++){
        cout << a[i];
      }
      sort(sol.begin(), sol.end());
      vector<long long>::iterator pos = upper_bound(sol.begin(), sol.end(), smallest);
      cout << sol[pos-sol.begin()];
      for(auto u:sol){
        if(u!=sol[pos-sol.begin()])
        cout << u ;
      }
      cout << endl;
    }
  }
}