1179A - Valeriy and Deque - CodeForces Solution

/*
Author :- Darshan Chaudhari ( SGGSIET Nanded ) 
------------------------------------------------------------------------------------------------------------
*/
#include <bits/stdc++.h>  // Global header file ;
#include<ext/pb_ds/assoc_container.hpp>  // Policy based Data Structures ;
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update> ;
/*
------------------------------------------------------------------------------------------------------------
Debugging Templates
------------------------------------------------------------------------------------------------------------
*/
template <typename T>std::ostream& operator<<(std::ostream& out, const std::vector<T>& vec) {if (vec.empty()) {out << "[]";return out;}out << '[';for (int i = 0; i < vec.size() - 1; i++) {out << vec[i] << ", ";}return out << vec.back() << ']';}template <typename T1, typename T2>std::ostream& operator<<(std::ostream& out, const std::pair<T1, T2>& pair) {return out << '(' << pair.first << ", " << pair.second << ')';}template <typename T>std::ostream& operator<<(std::ostream& out, const std::deque<T>& deq) {if (deq.empty()) {out << "[]";return out;}out << '[';for (int i = 0; i < deq.size() - 1; i++) {out << deq[i] << ", ";}return out << deq.back() << ']';}template <typename T1, typename T2>std::ostream& operator<<(std::ostream& out, const std::unordered_map<T1, T2>& map) {out << '{';for (auto it = map.begin(); it != map.end(); it++) {std::pair<T1, T2> element = *it;out << element.first << ": " << element.second;if (std::next(it) != map.end()){out << ", ";}}return out << '}';}template <typename T1, typename T2>std::ostream& operator<<(std::ostream& out, const std::map<T1, T2>& map){out<<'{';for (auto it = map.begin(); it != map.end(); it++) {std::pair<T1, T2> element = *it;out << element.first << ": " << element.second;if (std::next(it) != map.end()) {out << ", "; }}return out << '}';}template <typename T>std::ostream& operator<<(std::ostream& out, const std::unordered_set<T>& set) {out << '{';for (auto it = set.begin(); it != set.end(); it++) {T element = *it;out << element;if (std::next(it) != set.end()) {out << ", "; }}return out << '}';}template <typename T>std::ostream& operator<<(std::ostream& out, const std::multiset<T>& set) {out << '{';for (auto it = set.begin(); it != set.end(); it++) {T element = *it;out << element;if (std::next(it) != set.end()) {out << ", ";}}return out << '}';}template <typename T>std::ostream& operator<<(std::ostream& out, const std::unordered_multiset<T>& set) {out << '{';for (auto it = set.begin(); it != set.end(); it++) {T element = *it;out << element;if (std::next(it) != set.end()){out << ", ";}}return out << '}';}template <typename T>std::ostream& operator<<(std::ostream& out, const std::set<T>& set) {out << '{';for (auto it = set.begin(); it != set.end(); it++) {T element = *it;out << element;if (std::next(it) != set.end()){out << ", ";}}return out << '}';}template<typename Type, unsigned N, unsigned Last>struct TuplePrinter {static void print(std::ostream& out, const Type& value) {out << std::get<N>(value) << ", ";TuplePrinter<Type, N + 1, Last>::print(out, value);}};template<typename Type, unsigned N>struct TuplePrinter<Type, N, N> {static void print(std::ostream& out, const Type& value){out << std::get<N>(value);}};template<typename... Types>std::ostream& operator<<(std::ostream& out, const std::tuple<Types...>& value) {out << '(';TuplePrinter<std::tuple<Types...>, 0, sizeof...(Types) - 1>::print(out, value);return out << ')';}

bool double_equals(double a, double b, double epsilon = 0.000000000000001)
{
    return abs(a - b) < epsilon;
}
/*

------------------------------------------------------------------------------------------------------------
Macros
------------------------------------------------------------------------------------------------------------
*/
using ll = long long ;
using pii = pair<int, int> ;
using pll = pair<ll,ll>  ;
using vi = vector<int>  ;
using vl = vector<ll>; 
using vvi = vector<vi>;
using vvl = vector<vl>;
using vpi = vector<pii> ;
using vpl = vector<pll> ;
template <typename T> 
using minheap =  priority_queue <T, vector<T> ,greater<T>> ;
using maxheap =  priority_queue <int> ;
double EPS = 1e-9;
int infinite = 1000000005;
long long INFF = 1000000000000000005LL;
double PI = acos(-1);
int dirx[8] = { -1, 0, 0, 1, -1, -1, 1, 1 };
int diry[8] = { 0, 1, -1, 0, -1, 1, -1, 1 };
 
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
#define take(arr) for(int i=0; i<n; i++){cin>>arr[i] ;}
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define allrev(v) v.rbegin(), v.rend() ;
#define alla(arr, sz) arr, arr + sz
#define SIZE(v) (int)v.size()
#define sort(v) sort(all(v))
#define sortrev(v) sort(allrev(v))
#define rev(v) reverse(all(v))
#define sorta(arr, sz) sort(alla(arr, sz))
#define reva(arr, sz) reverse(alla(arr, sz))
#define PERMUTE next_permutation
#define TC(t) while (t--)


int main(){
    fastio ;
    ll n, q;
    cin>>n>>q ;
    vl arr(n) ;
    take(arr) ;
    ll i=0;
    ll j=1;
    vpl ans ;
    vl eliminated ;
    ll mx = *max_element(all(arr)) ;
    while(arr[i]!=mx ){
        if(i<j){
            ans.pb({arr[i], arr[j]}) ;
        }else{
            ans.pb({arr[j], arr[i]}) ;
        }
        if(arr[i] < arr[j]){
            eliminated.pb(arr[i]) ;
            i = j ;
            j++ ;
        }else{
            eliminated.pb(arr[j]) ;
            j++ ;
        }
    }
    // for(int i=0; i<ans.size(); i++){
    //     cout<<ans[i].first <<"  "<<ans[i].second<<"\n" ;
    // }
    // cout<<"\n" ;
    vl finalvec ;
    for(ll k = i+1; k<n; k++){
        finalvec.pb(arr[k]) ;
    }
    for(int i=0; i<eliminated.size(); i++){  //1000000 999998
                                             // 1000000 999999
        finalvec.pb(eliminated[i]) ;
    }
    // cout<<finalvec<<"\n" ;
    while(q--){
        ll query ;
        cin>>query ;
        if(query <= ans.size()){
            cout<<ans[query-1].first<<" "<<ans[query-1].second<<"\n" ;
        }else{
            query-=ans.size() ;
            query = (query - 1) % (n-1) ;
            cout<<mx<<" "<<finalvec[query]<<"\n" ;
        }
    }
    // cout<<mx<<"\n" ;
    return 0;
}