#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #ifdef LOCAL # include "debug_print.hpp" # define debug(...) debug_print::multi_print(#__VA_ARGS__, __VA_ARGS__) #else # define debug(...) (static_cast(0)) #endif using namespace std; #define rep(i,n) for(decltype(n) i=0; i<(n); i++) #define rrep(i,n) for(decltype(n) i=(n)-1; i>=0; i--) #define FOR(i,a,b) for(decltype(a) i=(a); i<(b); i++) #define RFOR(i,a,b) for(decltype(b) i=(b-1); i>=(a); i--) #define ALL(v) v.begin(), v.end() #define RALL(v) v.rbegin(), v.rend() #define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() ); #define pb push_back using ll = long long; using D = double; using LD = long double; using P = pair; template using PQ = priority_queue>; template using minPQ = priority_queue, greater>; templatebool chmax(T &a, const T &b) { if (abool chmin(T &a, const T &b) { if (b ostream &operator<<(ostream &os, const pair &p) { os << p.first << " " << p.second; return os; } template istream &operator>>(istream &is, pair &p) { is >> p.first >> p.second; return is; } template ostream &operator<<(ostream &os, const vector &v) { int s = (int)v.size(); for (int i = 0; i < s; i++) os << (i ? " " : "") << v[i]; return os; } template istream &operator>>(istream &is, vector &v) { for (auto &x : v) is >> x; return is; } void in() {} template void in(T &t, U &...u) { cin >> t; in(u...); } void out() { cout << "\n"; } template void out(const T &t, const U &...u) { cout << t; if (sizeof...(u)) cout << sep; out(u...); } void outr() {} template void outr(const T &t, const U &...u) { cout << t; outr(u...); } #line 1 "structure/wavelet/succinct-indexable-dictionary.hpp" /** * @brief Succinct Indexable Dictionary(完備辞書) */ struct SuccinctIndexableDictionary { size_t length; size_t blocks; vector< unsigned > bit, sum; SuccinctIndexableDictionary() = default; SuccinctIndexableDictionary(size_t length) : length(length), blocks((length + 31) >> 5) { bit.assign(blocks, 0U); sum.assign(blocks, 0U); } void set(int k) { bit[k >> 5] |= 1U << (k & 31); } void build() { sum[0] = 0U; for(int i = 1; i < blocks; i++) { sum[i] = sum[i - 1] + __builtin_popcount(bit[i - 1]); } } bool operator[](int k) { return (bool((bit[k >> 5] >> (k & 31)) & 1)); } int rank(int k) { return (sum[k >> 5] + __builtin_popcount(bit[k >> 5] & ((1U << (k & 31)) - 1))); } int rank(bool val, int k) { return (val ? rank(k) : k - rank(k)); } }; #line 2 "structure/wavelet/wavelet-matrix.hpp" /* * @brief Wavelet Matrix(ウェーブレット行列) * @docs docs/wavelet-matrix.md */ template< typename T, int MAXLOG > struct WaveletMatrix { size_t length; SuccinctIndexableDictionary matrix[MAXLOG]; int mid[MAXLOG]; WaveletMatrix() = default; WaveletMatrix(vector< T > v) : length(v.size()) { vector< T > l(length), r(length); for(int level = MAXLOG - 1; level >= 0; level--) { matrix[level] = SuccinctIndexableDictionary(length + 1); int left = 0, right = 0; for(int i = 0; i < length; i++) { if(((v[i] >> level) & 1)) { matrix[level].set(i); r[right++] = v[i]; } else { l[left++] = v[i]; } } mid[level] = left; matrix[level].build(); v.swap(l); for(int i = 0; i < right; i++) { v[left + i] = r[i]; } } } pair< int, int > succ(bool f, int l, int r, int level) { return {matrix[level].rank(f, l) + mid[level] * f, matrix[level].rank(f, r) + mid[level] * f}; } // v[k] T access(int k) { T ret = 0; for(int level = MAXLOG - 1; level >= 0; level--) { bool f = matrix[level][k]; if(f) ret |= T(1) << level; k = matrix[level].rank(f, k) + mid[level] * f; } return ret; } T operator[](const int &k) { return access(k); } // count i s.t. (0 <= i < r) && v[i] == x int rank(const T &x, int r) { int l = 0; for(int level = MAXLOG - 1; level >= 0; level--) { tie(l, r) = succ((x >> level) & 1, l, r, level); } return r - l; } // k-th(0-indexed) smallest number in v[l,r) T kth_smallest(int l, int r, int k) { assert(0 <= k && k < r - l); T ret = 0; for(int level = MAXLOG - 1; level >= 0; level--) { int cnt = matrix[level].rank(false, r) - matrix[level].rank(false, l); bool f = cnt <= k; if(f) { ret |= T(1) << level; k -= cnt; } tie(l, r) = succ(f, l, r, level); } return ret; } // k-th(0-indexed) largest number in v[l,r) T kth_largest(int l, int r, int k) { return kth_smallest(l, r, r - l - k - 1); } // count i s.t. (l <= i < r) && (v[i] < upper) int range_freq(int l, int r, T upper) { int ret = 0; for(int level = MAXLOG - 1; level >= 0; level--) { bool f = ((upper >> level) & 1); if(f) ret += matrix[level].rank(false, r) - matrix[level].rank(false, l); tie(l, r) = succ(f, l, r, level); } return ret; } // count i s.t. (l <= i < r) && (lower <= v[i] < upper) int range_freq(int l, int r, T lower, T upper) { return range_freq(l, r, upper) - range_freq(l, r, lower); } // max v[i] s.t. (l <= i < r) && (v[i] < upper) T prev_value(int l, int r, T upper) { int cnt = range_freq(l, r, upper); return cnt == 0 ? T(-1) : kth_smallest(l, r, cnt - 1); } // min v[i] s.t. (l <= i < r) && (lower <= v[i]) T next_value(int l, int r, T lower) { int cnt = range_freq(l, r, lower); return cnt == r - l ? T(-1) : kth_smallest(l, r, cnt); } }; template< typename T, int MAXLOG > struct CompressedWaveletMatrix { WaveletMatrix< int, MAXLOG > mat; vector< T > ys; CompressedWaveletMatrix(const vector< T > &v) : ys(v) { sort(begin(ys), end(ys)); ys.erase(unique(begin(ys), end(ys)), end(ys)); vector< int > t(v.size()); for(int i = 0; i < v.size(); i++) t[i] = get(v[i]); mat = WaveletMatrix< int, MAXLOG >(t); } inline int get(const T& x) { return lower_bound(begin(ys), end(ys), x) - begin(ys); } T access(int k) { return ys[mat.access(k)]; } T operator[](const int &k) { return access(k); } int rank(const T &x, int r) { auto pos = get(x); if(pos == ys.size() || ys[pos] != x) return 0; return mat.rank(pos, r); } T kth_smallest(int l, int r, int k) { return ys[mat.kth_smallest(l, r, k)]; } T kth_largest(int l, int r, int k) { return ys[mat.kth_largest(l, r, k)]; } int range_freq(int l, int r, T upper) { return mat.range_freq(l, r, get(upper)); } int range_freq(int l, int r, T lower, T upper) { return mat.range_freq(l, r, get(lower), get(upper)); } T prev_value(int l, int r, T upper) { auto ret = mat.prev_value(l, r, get(upper)); return ret == -1 ? T(-1) : ys[ret]; } T next_value(int l, int r, T lower) { auto ret = mat.next_value(l, r, get(lower)); return ret == -1 ? T(-1) : ys[ret]; } }; int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); int n; in(n); vector x(n); in(x); CompressedWaveletMatrix wm(x); int q; in(q); rep(_,q){ int l,r,y; in(l,r,y); l--; int ok = 0, ng = 1e9+1; while(ng-ok > 1){ int mid = (ok+ng)/2; if(wm.range_freq(l,r,y-mid+1,y+mid) == 0) ok = mid; else ng = mid; } out(ok); } }