#1150695 (C++23) No.3467 Bracket Warp

• 問題: No.3467 Bracket Warp
• ユーザー: rogi52
• 提出日時: 2026-02-28 16:28:23
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: WA
• 実行時間: -
• コード長: 22,155 bytes
• コンパイル時間: 4,950 ms
• コンパイル使用メモリ: 365,704 KB
• 実行使用メモリ: 18,880 KB
• 最終ジャッジ日時: 2026-02-28 16:28:47
• 合計ジャッジ時間: 10,778 ms
• ジャッジサーバーID （参考情報）: judge3 / judge7

ファイルパターン	結果
sample	AC * 2
other	AC * 18 WA * 7

ソースコード

#line 2 "/Users/korogi/Desktop/cp-cpp/template.hpp"
#include <bits/stdc++.h>
using namespace std;

using i32 = int;
using i64 = long long;
using i128 = __int128;
using u32 = unsigned int;
using u64 = unsigned long long;
using u128 = unsigned __int128;
using f32 = double;
using f64 = long double;

#define DMP(x) cout << "[" << __LINE__ << "]" << " " << #x << ":" << " " << x << endl;

#define FOR1(n)          for(int _ =  0 , n_ = (n); _ < n_; _++)
#define FOR2(i, n)       for(int i =  0 , n_ = (n); i < n_; i++)
#define FOR3(i, s, t)    for(int i = (s), t_ = (t); i < t_; i++)
#define FOR4(i, s, t, d) for(int i = (s), t_ = (t), d_ = (d); i < t_; i += d_)
#define OVERLOAD4(a, b, c, d, e, ...) e
#define FOR(...) OVERLOAD4(__VA_ARGS__, FOR4, FOR3, FOR2, FOR1)(__VA_ARGS__)

#define REV1(n)          for(int _ = (n) - 1; _ >=  0 ; _--)
#define REV2(i, n)       for(int i = (n) - 1; i >=  0 ; i--)
#define REV3(i, s, t)    for(int i = (t) - 1, s_ = (s); i >= s_; i--)
#define REV4(i, s, t, d) for(int i = (t) - 1, s_ = (s), d_ = (d); i >= s_; i -= d_)
#define OVERLOAD3(a, b, c, d, ...) d
#define REV(...) OVERLOAD4(__VA_ARGS__, REV4, REV3, REV2, REV1)(__VA_ARGS__)

#define FOR_SUBSET(T, S) for(int S_ = (S), T = S_; T >= 0; T = (T == 0 ? -1 : (T - 1) & S_))

#define MULTI for(int testcase_ = in(), testcase = 0; testcase < testcase_; testcase++) [&]

template < class T > using heap_max = priority_queue< T, vector< T >, less< T > >;
template < class T > using heap_min = priority_queue< T, vector< T >, greater< T >>;

template < class T, class U > bool chmin(T& a, const U& b) { return a > b ? a = b, 1 : 0; }
template < class T, class U > bool chmax(T& a, const U& b) { return a < b ? a = b, 1 : 0; }

i64 floor_div(const i64 n, const i64 d) { assert(d != 0); return n / d - ((n ^ d) <  0 && n % d != 0); }
i64  ceil_div(const i64 n, const i64 d) { assert(d != 0); return n / d + ((n ^ d) >= 0 && n % d != 0); }

template < class T, class F > T bin_search(T ok, T ng, const F& check) { while((ok > ng ? ok - ng : ng - ok) > 1) { T mid = (ok + ng) / 2; (check(mid) ? ok : ng) = mid; } return ok; }
template < class T, class F > T bin_search_real(T ok, T ng, const F& check, int step = 100) { FOR(step) { T mid = (ok + ng) / 2; (check(mid) ? ok : ng) = mid; } return ok; }

template < class T, class U > T accum(const vector< U >& a) { return accumulate(a.begin(), a.end(), T(0)); }
template < class T > void sort(vector< T >& a) { sort(a.begin(), a.end()); }
template < class T > void rsort(vector< T >& a) { sort(a.rbegin(), a.rend()); }
template < class T > void reverse(vector< T >& a) { reverse(a.begin(), a.end()); }
void sort(string& s) { sort(s.begin(), s.end()); }
void rsort(string& s) { sort(s.rbegin(), s.rend()); }
void reverse(string& s) { reverse(s.begin(), s.end()); }
template < class T, class Cmp > void sort(vector< T >& a, Cmp cmp) { sort(a.begin(), a.end(), cmp); }
template < class T > int LB(const vector< T >& a, T x) { return distance(a.begin(), lower_bound(a.begin(), a.end(), x)); }
template < class T > int UB(const vector< T >& a, T x) { return distance(a.begin(), upper_bound(a.begin(), a.end(), x)); }
template < class T > void unique(vector< T >& a) { sort(a.begin(), a.end()); a.erase(unique(a.begin(), a.end()), a.end()); }
vector<int> iota(int n) { vector<int> a(n); iota(a.begin(), a.end(), 0); return a; }

istream& operator >> (istream& is, i128& x) {
    string s; is >> s;
    int m = (s[0] == '-');
    x = 0;
    FOR(i, m, ssize(s)) x = x * 10 + (s[i] - '0');
    if(m) x *= -1;
    return is;
}
ostream& operator << (ostream& os, const i128& x) {
    if(x == 0) return os << '0';
    i128 y = x; if(y < 0) { os << '-'; y *= -1; }
    vector<int> ny;
    while(y) ny.push_back(y % 10), y /= 10;
    REV(i, ssize(ny)) os << ny[i];
    return os;
}
namespace scan {
struct x0 { template < class T > operator T() { T x; cin >> x; return x; } };
struct x1 { int n; x1(int n) : n(n) {} template < class T > operator vector< T >() { vector< T > a(n); for(T& x : a) cin >> x; return a; } };
struct x2 { int h, w; x2(int h, int w) : h(h), w(w) {} template < class T > operator vector< vector< T > >() { vector m(h, vector< T >(w)); for(vector< T >& a : m) for(T& x : a) cin >> x; return m; } };
struct cppio { cppio() { cin.tie(0); ios::sync_with_stdio(0); } } cppio_instance;
}
scan::x0 in() { return scan::x0(); }
scan::x1 in(int n) { return scan::x1(n); }
scan::x2 in(int h, int w) { return scan::x2(h, w); }

template < class T > ostream& operator << (ostream& os, const vector< T >& a) {
    const int n = a.size();
    FOR(i, n) { os << a[i]; if(i + 1 != n) os << ' '; }
    return os;
}
template < class T > int print_n(const vector< T >& a) { for(const T& x : a) cout << x << '\n'; return 0; }
int print() { cout << '\n'; return 0; }
template < class Head, class... Tail > int print(Head&& h, Tail&&... t) { cout << h; if(sizeof...(Tail)) cout << ' '; return print(forward<Tail>(t)...); }
namespace printer {
    void prec(int n) { cout << fixed << setprecision(n); }
    void flush() { cout.flush(); }
}

vector<int>& operator ++ (vector<int>& a) { for(auto& e : a) e++; return a; }
vector<int>& operator -- (vector<int>& a) { for(auto& e : a) e--; return a; }
vector<int>  operator ++ (vector<int>& a, int) { vector<int> b = a; ++a; return b; }
vector<int>  operator -- (vector<int>& a, int) { vector<int> b = a; --a; return b; }

template < class T > vector<pair< T, int>> RLE(const vector< T >& a) { vector<pair< T, int>> v; for(const T& x : a) { if(not v.empty() and v.back().first == x) v.back().second++; else v.emplace_back(x, 1); } return v; }
vector<pair<char, int>> RLE(const string& s) { vector<pair<char, int>> v; for(const char& c : s) { if(not v.empty() and v.back().first == c) v.back().second++; else v.emplace_back(c, 1); } return v; }
template < class String, class Same > vector<String> RLE(const String& a, const Same same) { vector<String> v; for(const auto& x : a) { if(not v.empty() and same(v.back().back(), x)) v.back().push_back(x); else v.push_back({x}); } return v; }

int YESNO(bool yes) { return print(yes ? "YES" : "NO"); }
int YesNo(bool yes) { return print(yes ? "Yes" : "No"); }
int Yes() { return print("Yes"); }
int No() { return print("No"); }

constexpr i32 INF32 = 1e9;
constexpr i64 INF64 = 1e18;
template < class T > constexpr T infty = 0;
template <> constexpr int infty<int> = 1e9;
template <> constexpr int infty<u32> = 1e9;
template <> constexpr i64 infty<i64> = 1e18;
template <> constexpr u64 infty<u64> = 1e18;

namespace bit {
int pop(int x) { return popcount<u32>(x); }
int pop(u32 x) { return popcount<u32>(x); }
int pop(i64 x) { return popcount<u64>(x); }
int pop(u64 x) { return popcount<u64>(x); }
int parity(int x) { return __builtin_parity(x); }
int parity(u32 x) { return __builtin_parity(x); }
int parity(i64 x) { return __builtin_parityll(x); }
int parity(u64 x) { return __builtin_parityll(x); }
int sgn(int x) { return parity(x) ? -1 : +1; }
int sgn(u32 x) { return parity(x) ? -1 : +1; }
int sgn(i64 x) { return parity(x) ? -1 : +1; }
int sgn(u64 x) { return parity(x) ? -1 : +1; }
int top(int x) { return x == 0 ? -1 : 31 - __builtin_clz(x); }
int top(u32 x) { return x == 0 ? -1 : 31 - __builtin_clz(x); }
int top(i64 x) { return x == 0 ? -1 : 63 - __builtin_clzll(x); }
int top(u64 x) { return x == 0 ? -1 : 63 - __builtin_clzll(x); }
int low(int x) { return x == 0 ? -1 : __builtin_ctz(x); }
int low(u32 x) { return x == 0 ? -1 : __builtin_ctz(x); }
int low(i64 x) { return x == 0 ? -1 : __builtin_ctzll(x); }
int low(u64 x) { return x == 0 ? -1 : __builtin_ctzll(x); }
int ceil(int x) { return bit_ceil<u32>(x); }
i64 ceil(i64 x) { return bit_ceil<u64>(x); }
int floor(int x) { return bit_floor<u32>(x); }
i64 floor(i64 x) { return bit_floor<u64>(x); }
}

// (-1)^n
int parity_sign(int n) { return n % 2 == 0 ? +1 : -1; }

// template < class T > pair< T, int > min(const vector< T >& a) { auto itr = min_element(a.begin(), a.end()); return {*itr, itr - a.begin()}; }
// template < class T > pair< T, int > max(const vector< T >& a) { auto itr = max_element(a.begin(), a.end()); return {*itr, itr - a.begin()}; }

template < class Key, class Value >
struct key_value {
    Key key;
    Value value;
};
template < class Value > key_value<int, Value> min(const vector<Value>& a) {
    assert(1 <= ssize(a));
    auto itr = min_element(a.begin(), a.end());
    return {static_cast<int>(distance(a.begin(), itr)), *itr};
}
template < class Value > key_value<int, Value> max(const vector<Value>& a) {
    assert(1 <= ssize(a));
    auto itr = max_element(a.begin(), a.end());
    return {static_cast<int>(distance(a.begin(), itr)), *itr};
}

struct grid {
    int H, W;
    grid(int H, int W) : H(H), W(W) {}
    static constexpr pair<int, int> dir4[] = {
                  {-1,  0}, 
        { 0, -1},           { 0, +1}, 
                  {+1,  0}
    };
    static constexpr pair<int, int> dir8[] = {
        {-1, -1}, {-1,  0}, {-1, +1},
        { 0, -1},           { 0, +1},
        {+1, -1}, {+1,  0}, {+1, +1}
    };
    bool contains(int i, int j) const {
        return 0 <= i and i < H and 0 <= j and j < W;
    }
    template < class F > 
    void for_each_dir4(int i, int j, const F& f) const {
        for(const auto [di, dj] : dir4) {
            const int ni = i + di, nj = j + dj;
            if(contains(ni, nj)) f(ni, nj);
        }
    }
    template < class F >
    void for_each_dir8(int i, int j, const F& f) const {
        for(const auto [di, dj] : dir8) {
            const int ni = i + di, nj = j + dj;
            if(contains(ni, nj)) f(ni, nj);
        }
    }
};

template < class Sum > struct psum1D {
    int n;
    vector<Sum> s;
    psum1D() : n(0), s(1, Sum()) {}
    template < class Value >
    psum1D(const vector<Value>& a) : n(ssize(a)), s(n + 1, Sum()) {
        FOR(i, n) s[i + 1] = s[i] + static_cast<Sum>(a[i]);
    }
    // [l, r)
    Sum v(int l, int r) const {
        assert(0 <= l and l <= r and r <= n);
        return s[r] - s[l];
    }
    void push_back(const Sum& x) {
        s.push_back(s.back() + x);
        n += 1;
    }
};

template < class Value > struct psum2D {
    int H, W;
    vector<vector<Value>> A;
    bool built;
    psum2D(int H, int W) : H(H), W(W), A(H + 1, vector(W + 1, Value(0))), built(false) {}
    // A[x][y] += v
    void add(int x, int y, Value v) {
        assert(not built);
        assert(0 <= x and x < H);
        assert(0 <= y and y < W);
        A[x + 1][y + 1] += v;
    }
    void build() {
        FOR(x, H) FOR(y, W + 1) A[x + 1][y] += A[x][y];
        FOR(x, H + 1) FOR(y, W) A[x][y + 1] += A[x][y];
        built = true;
    }
    // [xL, xR) * [yL, yR)
    Value sum(int xL, int xR, int yL, int yR) {
        assert(built);
        assert(0 <= xL and xL <= xR and xR <= H);
        assert(0 <= yL and yL <= yR and yR <= W);
        return A[xR][yR] - A[xR][yL] - A[xL][yR] + A[xL][yL];
    }
    Value get(int x, int y) {
        assert(built);
        assert(0 <= x and x < H);
        assert(0 <= y and y < W);
        return sum(x, x + 1, y, y + 1);
    }
};
template < class Value > struct imos2D {
    int H, W;
    vector<vector<Value>> A;
    bool built;
    imos2D(int H, int W) : H(H), W(W), A(H + 1, vector(W + 1, Value(0))), built(false) {}
    void add(int xL, int xR, int yL, int yR, Value v) {
        assert(not built);
        assert(0 <= xL and xL <= xR and xR <= H);
        assert(0 <= yL and yL <= yR and yR <= W);
        A[xL][yL] += v;
        A[xR][yL] -= v;
        A[xL][yR] -= v;
        A[xR][yR] += v;
    }
    void build() {
        assert(not built);
        FOR(i, H + 1) FOR(j, W) A[i][j + 1] += A[i][j];
        FOR(i, H) FOR(j, W + 1) A[i + 1][j] += A[i][j];
        built = true;
    }
    Value get(int x, int y) {
        assert(built);
        assert(0 <= x and x < H);
        assert(0 <= y and y < W);
        return A[x][y];
    }
};

#line 3 "/Users/korogi/Desktop/cp-cpp/rnd.hpp"

namespace rnd {
    u32 seed; mt19937 mt;
    struct gen_seed { gen_seed() { seed = random_device()(); mt = mt19937(seed); } } gen_seed_instance;
    // [L, R)
    template < class Int > Int i(Int L, Int R) { assert(L < R); return uniform_int_distribution<Int>(L, R - 1)(mt); }
    template < class Real > Real r(Real L, Real R) { assert(L <= R); return uniform_real_distribution<Real>(L, R)(mt); }
}

template < int n, array<u32, n> mod > struct hash_vector {
    array<u32, n> a;
    using hvec = hash_vector;
    hvec& s(array<u32, n> a) { FOR(i, n) this->a[i] = a[i] < mod[i] ? a[i] : a[i] - mod[i]; return *this; }
    hash_vector(u32 v = 0) { FOR(i, n) a[i] = v % mod[i] + mod[i]; s(a); }
    hvec operator - () const { return hvec() - *this; }
    hvec& operator += (const hvec& r) { FOR(i, n) a[i] += r.a[i]; return s(a); }
    hvec& operator -= (const hvec& r) { FOR(i, n) a[i] += mod[i] - r.a[i]; return s(a); }
    hvec& operator *= (const hvec& r) { FOR(i, n) a[i] = u64(a[i]) * r.a[i] % mod[i]; return *this; }
    hvec& operator /= (const hvec& r) { return *this *= inv(r); }
    hvec operator + (const hvec& r) const { return hvec(*this) += r; }
    hvec operator - (const hvec& r) const { return hvec(*this) -= r; }
    hvec operator * (const hvec& r) const { return hvec(*this) *= r; }
    hvec operator / (const hvec& r) const { return hvec(*this) /= r; }
    bool operator == (const hvec& r) const { return a == r.a; }
    bool operator != (const hvec& r) const { return a != r.a; }
    bool operator < (const hvec& r) const { return a < r.a; }
};
template < int n, array<u32, n> mod > hash_vector<n, mod> pow(hash_vector<n, mod> x, u64 m) {
    hash_vector<n, mod> p(1);
    for(; m; m >>= 1) { if(m & 1) p *= x; x *= x; }
    return p;
}
template < int n, array<u32, n> mod > hash_vector<n, mod> inv(hash_vector<n, mod> x) {
    hash_vector<n, mod> res;
    FOR(i, n) {
        u32 a = x.a[i], b = mod[i], u = 1, v = 0;
        while(b) { u32 t = a / b; swap(a -= t * b, b); swap(u -= t * v, v); }
        res[i] = u;
    }
    return res;
}
template < int n, array<u32, n> mod > ostream& operator << (ostream& os, const hash_vector< n, mod >& x) { FOR(i, n) { if(i) os << ' '; os << x.a[i]; } return os; }
using hvec1 = hash_vector< 1, array<u32, 1>{999999937} >;
using hvec2 = hash_vector< 2, array<u32, 2>{999999937, 1000000007} >;
using hvec3 = hash_vector< 3, array<u32, 3>{999999937, 1000000007, 1000000009} >;
using hvec4 = hash_vector< 4, array<u32, 4>{999999937, 1000000007, 1000000009, 1000000021} >;
#line 280 "/Users/korogi/Desktop/cp-cpp/template.hpp"

namespace r52 {
int abs(int x) { return x >= 0 ? x : -x; }
i64 abs(i64 x) { return x >= 0 ? x : -x; }
i128 abs(i128 x) { return x >= 0 ? x : -x; }
}
#line 2 "/Users/korogi/Desktop/cp-cpp/ds/uf.hpp"

struct union_find {
    int num_c; // 連結成分の個数
    vector<int> data;
    static constexpr int SKIP = -1;
    union_find() {}
    union_find(int n) : num_c(n), data(n, -1) {}

    int unite(int x, int y) {
        x = root(x), y = root(y);
        if(x == y) return SKIP;
        num_c--;
        if(size(x) < size(y)) swap(x, y);
        data[x] += data[y];
        return data[y] = x;
    }
    int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); }
    int size(int x) { return -data[root(x)]; }
    bool same(int x, int y) { return root(x) == root(y); }

    // merge(x, y): s[x] <- s[x] + s[y]
    template < class F >
    int unite(int x, int y, const F& merge) {
        x = root(x), y = root(y);
        if(x == y) return SKIP;
        num_c--;
        if(size(x) < size(y)) swap(x, y);
        data[x] += data[y];
        data[y] = x;
        merge(x, y); // s[x] <- s[x] + s[y]
        return x;
    }
};
#line 3 "/Users/korogi/Desktop/cp-cpp/tree/hld.hpp"

struct treeHLD {
    int n, root;
    struct edge { int to, i; };
    vector<vector<edge>> g;
    treeHLD(int n) : n(n), g(n), S(n, 0), D(n, 0), L(n, -1), R(n, -1), E(n, -1), id(0), decomped(0) {}
    void add_edge(int u, int v, int i = 0) {
        g[u].push_back({v, i});
        g[v].push_back({u, i});
    }
    void decomp(int r = 0) {
        root = r;
        nxt.assign(n, r);
        par.assign(n, r);
        dfs0(r);
        dfs1(r);
        decomped = true;
    }

    template < class Func > void path_query_comm(int u, int v, bool vertex, const Func& f) const {
        assert(decomped);
        const int x = lca(u, v);
        for(auto [a, b] :  ascend(u, x)) tie(a, b) = minmax({a, b}), f(a, b);
        if(vertex) f(L[x], L[x] + 1);
        for(auto [a, b] : descend(x, v)) tie(a, b) = minmax({a, b}), f(a, b);
    }
    template < class Func > void path_query(int u, int v, bool vertex, const Func& f) const {
        assert(decomped);
        const int x = lca(u, v);
        for(auto [a, b] :  ascend(u, x)) f(a, b);
        if(vertex) f(L[x], L[x] + 1);
        for(auto [a, b] : descend(x, v)) f(a, b);
    }
    template < class Func > void subtree_query(int v, bool vertex, const Func& f) const {
        assert(decomped);
        f(L[v] + !vertex, R[v]);
    }

    // v != root ? parent[v] : -1
    int parent(int v) const {
        assert(decomped);
        return v == root ? -1 : par[v];
    }
    int la(int v, int d) const {
        assert(decomped);
        while(v != -1) {
            const int u = nxt[v];
            if(L[u] <= L[v] - d) return E[L[v] - d];
            d -= L[v] - L[u] + 1;
            v = parent(u);
        }
        return v;
    }
    int lca(int u, int v) const {
        assert(decomped);
        for(; nxt[u] != nxt[v]; u = par[nxt[u]]) if(L[u] < L[v]) swap(u, v);
        return D[u] < D[v] ? u : v;
    }
    // 辺の本数
    int dist(int u, int v) const {
        assert(decomped);
        return D[u] + D[v] - D[lca(u, v)] * 2;
    }
    int jump(int u, int v, int d) const {
        assert(decomped);
        const int D_x = D[lca(u, v)];
        if(d <= D[u] - D_x) return la(u, d);
        d -= D[u] - D_x;
        if(d <= D[v] - D_x) return la(v, D[v] - D_x - d);
        return -1;
    }
    int in_subtree(int r, int v) const {
        assert(decomped);
        return L[r] < L[v] and R[v] <= R[r];
    }
    pair<int, int> seq_seg(int v) const {
        assert(decomped);
        return {L[v], R[v]};
    }
    int seq_pos(int v) const {
        assert(decomped);
        return L[v];
    }
    int seq_end(int v) const {
        assert(decomped);
        return R[v];
    }
    int depth(int v) const {
        assert(decomped);
        return D[v];
    }
    int subtree_size(int v) const {
        assert(decomped);
        return S[v];
    }
    int euler(int i) const {
        assert(decomped);
        return E[i];
    }
    bool is_decomped() const {
        return decomped;
    }

  private:
    int id, decomped;
    vector<int> S, D, L, R, nxt, par, E;
    void dfs0(int v) {
        S[v] = 1;
        for(edge& e : g[v]) {
            if(e.to == par[v]) {
                if(ssize(g[v]) >= 2 and e.to == g[v][0].to) swap(g[v][0], g[v][1]);
                else continue;
            }
            D[e.to] = D[v] + 1;
            par[e.to] = v;
            dfs0(e.to);
            S[v] += S[e.to];
            if(S[e.to] > S[g[v][0].to]) swap(e, g[v][0]);
        }
    }
    void dfs1(int v) {
        L[v] = id++;
        E[L[v]] = v;
        for(edge e : g[v]) if(e.to != par[v]) {
            nxt[e.to] = (e.to == g[v][0].to ? nxt[v] : e.to);
            dfs1(e.to);
        }
        R[v] = id;
    }
    vector<pair<int, int>> ascend(int u, int v) const {
        assert(decomped);
        vector<pair<int, int>> res;
        for(; nxt[u] != nxt[v]; u = par[nxt[u]]) res.push_back({L[u] + 1, L[nxt[u]]});
        if(u != v) res.push_back({L[u] + 1, L[v] + 1});
        return res;
    }
    vector<pair<int, int>> descend(int u, int v) const {
        assert(decomped);
        if(u == v) return {};
        if(nxt[u] == nxt[v]) return {{L[u] + 1, L[v] + 1}};
        vector<pair<int, int>> res = descend(u, par[nxt[v]]);
        res.push_back({L[nxt[v]], L[v] + 1});
        return res;
    }

};
#line 4 "a.cpp"

int main() {
    string S = in();
    S = '(' + S + ')';
    const int N = ssize(S);

    vector<int> opp(N);
    {
        stack<int> I;
        FOR(i, N) {
            if(S[i] == '(') {
                I.push(i);
            } else {
                assert(not I.empty());
                const int j = I.top(); I.pop();
                opp[i] = j;
                opp[j] = i;
            }
        }
    }
    vector<int> idx(N, -1);
    int M = 0;
    FOR(i, N) {
        if(i < opp[i]) {
            idx[i] = M++;
        } else {
            idx[i] = idx[opp[i]];
        }
    }
    treeHLD tree(M);
    vector<vector<int>> G(M);
    vector<int> pos(M, -1);
    {
        vector<int> I;
        FOR(i, N) {
            if(S[i] == '(') {
                if(not I.empty()) {
                    const int p = idx[I.back()];
                    const int v = idx[i];
                    tree.add_edge(p, v);
                    pos[v] = ssize(G[p]);
                    G[p].push_back(v);
                }
                I.push_back(i);
            } else {
                assert(not I.empty());
                I.pop_back();
            }
        }
    }
    tree.decomp(0);

    vector<int> W(M, 0);
    auto dfs = [&](auto dfs, int v, int d) -> void {
        W[v] = d;
        const int K = ssize(G[v]);
        FOR(i, K) {
            const int to = G[v][i];
            dfs(dfs, to, d + min(i + 1, K - i));
        }
    };
    dfs(dfs, 0, 0);

    int Q = in();
    FOR(Q) {
        int L = in(), R = in();
        L = idx[L];
        R = idx[R];
        if(L == R) {
            print(0);
        } else {
            const int X = tree.lca(L, R);
            if(L == X or R == X) {
                print(abs(W[L] - W[R]));
            } else {
                const int A = tree.jump(X, L, 1);
                const int B = tree.jump(X, R, 1);
                const int I = pos[A];
                const int J = pos[B];
                const int K = ssize(G[X]);
                const int D = min(abs(I - J), K + 1 - abs(I - J));
                print(W[L] - W[A] + W[R] - W[B] + D);
            }
        }
    }
}