#include <iostream>
#include <algorithm>
#include <tuple>

int main(){
  int a[] = { 123, 456, 678, 135, 564, 55, 5610 };
  int idx = 0;
  std::vector< std::tuple<int,int> > vec;

  std::transform( std::begin(a), std::end(a),
      std::back_inserter(vec),
      [&]( int v ){ return std::make_tuple( v, idx++); }
  );

  std::sort( vec.begin(), vec.end() );
  for( auto & v : vec ){
    std::cout << std::get<0>(v) << " " << std::get<1>(v) << "\n";
  }

  return 0;
}