#include <bits/stdc++.h>

using ll = long long;
#define int ll

template <typename T>
struct sparse_table {
    using size_t = std::size_t;
    template <typename U>
    using vector = std::vector<U>;

    size_t sz;
    vector<vector<size_t>> min;
    vector<size_t> log2;

    sparse_table() {}

    template <typename iterator>
    sparse_table(iterator first, iterator last)
        : sz(distance(first, last)), min(1, vector<size_t>(sz)) {
        initialize(first);
    }

    template <typename iterator>
    void initialize(iterator dat) {
        log2.resize(sz + 2);
        log2[1] = 0;
        for (size_t i = 2; i < sz + 2; ++i) {
            log2[i] = log2[i / 2] + 1;
        }
        if (sz) min.reserve(log2[(sz + 1) / 2] + 2);
        std::iota(min[0].begin(), min[0].end(), 0);
        for (size_t i = 1; i < 30; ++i) {
            size_t w = 1 << i;
            if (sz + 1 < w) break;
            vector<size_t> next(sz + 1 - w);
            for (size_t l = 0; l < sz + 1 - w; ++l) {
                size_t left = min[i - 1][l], right = min[i - 1][l + w / 2];
                next[l] = dat[left] < dat[right] ? left : right;
            }
            min.emplace_back(move(next));
        }
    }

    template <typename Container>
    size_t rmq(Container const &x, size_t l, size_t r) const {
        size_t i = log2[r - l];
        size_t rr = r - (1 << i);
        l = min[i][l], r = min[i][rr];
        return x[l] < x[r] ? l : r;
    }
};

using namespace std;

vector<int> solve(const vector<int> &a, const vector<pair<int, int>> &qs) {
    int n = a.size();
    vector<int> ds;
    for (int i = 1; i < n; ++i) {
        ds.push_back(a[i] - a[i - 1]);
    }

    const auto st = sparse_table<int>(ds.begin(), ds.end());
    vector<int> ans;
    for (auto q : qs) {
        int l, r;
        tie(l, r) = q;
        int idx = st.rmq(ds, l, r);
        ans.push_back(ds[idx] >= 0 ? 1 : 0);
    }
    return ans;
}

signed main() {
    int n;
    cin >> n;
    vector<int> a(n);
    // forall non-negative? non-positive?
    for (auto &x : a) cin >> x;
    {
        map<int, int> mp;
        for (auto &x : a) mp[x] = 0;
        int i = 0;
        for (auto &p : mp) p.second = i++;
        for (auto &x : a) x = mp[x];
    }
    int q;
    cin >> q;
    vector<pair<int, int>> qs(q);
    for (auto &q : qs) {
        int l, r;
        cin >> l >> r;
        q = make_pair(l, r);
    }
    vector<int> xs = solve(a, qs);
    for (auto &x : a) x = -x;
    vector<int> ys = solve(a, qs);

    for (int i = 0; i < q; ++i) {
        cout << xs[i] << ' ' << ys[i] << '\n';
    }
}