#pragma GCC optimize("O3", "unroll-loops")

#include <bits/stdc++.h>

using namespace std;

#include <ext/pb_ds/assoc_container.hpp>

#include <ext/pb_ds/tree_policy.hpp>

#define FILES freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout)

#define FAST ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)

#define FIXED cout << fixed << setprecision(20)

#define RANDOM srand(time(nullptr))

#define sz(a) (int)a.size()

#define int long long

#define rep(i,a,b) for(int i=(int)a;i<=(int)b;i++)

#define sep(i,a,b) for(int i=(int)a;i>=(int)b;i--)

#define inf 0x3f3f3f3f

#define mp make_pair

#define pb push_back

#define eb emplace_back

#define pf push_front

#define popb pop_back

#define popf pop_front

#define lb lower_bound

#define ub upper_bound

#define all(a) a.begin(),a.end()

#define ff first

#define ss second

#define endl "\n"

#define n6 3000005

#define n3 3005

#define n5 300005

#define pi pair<int,int>

#define pii pair<int,pi>

template<typename T>

using ordered_set = __gnu_pbds::tree<T, __gnu_pbds::null_type, less<T>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>; // find_by_order(), order_of_key()

#define dbg1(x) cout << #x << ": " << x << endl;

#define dbg2(x, y) cout << #x << ": " << x << " | " << #y << ": " << y << endl;

#define dbg3(x, y, z) cout << #x << ": " << x << " | " << #y << ": " << y << " | " << #z << ": " << z << endl;

#define dbg4(a, b, c, d) cout << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << endl;

#define dbg5(a, b, c, d, e) cout << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << endl;

#define dbg6(a, b, c, d, e, f) cout << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << " | " << #f << ": " << f << endl;

#define dbg(...) fprintf(stderr, __VA_ARGS__)

#define dbgv(x) cout << #x << " = " << x << endl

#define dbga(arr, len) {cout << #arr << " = "; for (int _ = 0; _ < len; _++)cout << arr[_] << " "; cout << endl;}

#define dbgi(it) {cout << #it << " = "; for (const auto& _ : it)cout << _ << " "; cout << endl;}

template <typename T> inline void ckmax(T &x, T y) {if (y > x) x = y; }

template <typename T> inline void ckmin(T &x, T y) {if (y < x) x = y; }

#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }

void err(istream_iterator<string> it) {}

template<typename T, typename... Args>

void err(istream_iterator<string> it, T a, Args... args) {

cout << *it << " =: " << a << endl;

err(++it, args...);

}

template <typename T1, typename T2>

inline std::ostream& operator << (std::ostream& os, const std::pair<T1, T2>& buf) {

return os << "(" << buf.first << ": " << buf.second << ")";

}

template<typename T>

inline std::ostream &operator << (std::ostream & os,const std::vector<T>& v) {

bool first = true;

os << "[";

for(unsigned int i = 0; i < v.size(); i++) {

if(!first) os << ", ";

os << v[i];

first = false;

}

return os << "]";

}

template<typename T>

inline std::ostream &operator << (std::ostream & os,const std::set<T>& v) {

bool first = true;

os << "{";

for (typename std::set<T>::const_iterator ii = v.begin(); ii != v.end(); ++ii) {

if(!first) os << ", ";

os << *ii;

first = false;

}

return os << "}";

}

template<typename T1, typename T2>

inline std::ostream &operator << (std::ostream & os,const std::map<T1, T2>& v) {

bool first = true;

os << "{";

for (typename std::map<T1, T2>::const_iterator ii = v.begin(); ii != v.end(); ++ii) {

if(!first) os << ", ";

os << *ii ;

first = false;

}

return os << "}";

}

template<typename T>

inline std::ostream &operator << (std::ostream & os,const vector<vector<T>>& v) {

os << '\n';

for (auto &u: v) os << u << '\n';

return os;

}

const int MOD = 1e9 + 7;

const long long INF = 1e18;

const double EPS = 1e-6;

inline int add(int a, int b) {

}

inline int sub(int a, int b) {

}

inline int mul(int a, int b) {

return (long long) a * b % MOD;

}

inline int power(int a, long long b) {

}

void showdq(deque <int> g)

}

void showstack(stack <int> s)

}

void showqueue(queue<int> q)

}

int solve_util(deque<int> &q){

}

void nextGreater(int arr[], int n, int next[], char order)

}

void nextSmallerOfNextGreater(int arr[], int n)

}

int l[n6], r[n6], arr[n6];

int n;

void solve(){

}

signed main()