#define _CRT_SECURE_NO_WARNINGS
#pragma GCC Optimize("Ofast")
#include <iostream>
#include <vector>
#include <set>
#include <string>
#include <time.h>
#include <unordered_set>
#include <map>
#include <queue>
#include <algorithm>
#include <fstream>
#include <cstddef>
#include <cstdio>
#include <iostream>
#include <memory>
#include <stdexcept>
#include <string>
#include <array>
using namespace std;

#define vi vector<int>
#define vec vector
char open[256] = {}, close[256] = {};
int go(string s) {

    vec<char> st;
    deque<char> cur;
    vec<int> st2;
    string res;
    int x = 0, ans = 0;
    // Особо не отличается от проверки на правильность
    for (int i = 0; i < s.length(); ++i) {
        if (open[s[i]]) {
            cur.push_back(s[i]);
            st2.push_back(x);
            x = 0;
            st.push_back(close[s[i]]);
        }
        else {
            if (st.size() && st.back() == s[i]) {
                cur.push_back(s[i]);
                st.pop_back();
                x = st2.back();
                ++x;
                st2.pop_back();
                ans += x;
            }
            else {
                while (st.size()) cur.pop_front(), st.pop_back(), st2.pop_back();
                x = 0;
                if (res.size() < cur.size())
                {
                    res = "";
                    for (auto& e : cur)
                        res += e;
                }
                cur.clear();
            }
        }
    }
    //if (!st.size())++ans;
    while (st.size()) cur.pop_back(), st.pop_back(), ans += st2.back() + 1, st2.pop_back();
    if (res.size() < cur.size())
    {
        res = "";
        for (auto& e : cur)
            res += e;
    }
    return ans;
}

int go2(string s) {
    int n = s.length();
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        vec<char> st;
        int ok = 1;
        for (int j = i; j < n; ++j) {
            if (open[s[j]]) {
                st.push_back(close[s[j]]);
            }
            else {
                if (st.size() && st.back() == s[j]) {
                    st.pop_back();
                }
                else {
                    ok = 0; break;
                }
            }
            if (!st.size() && ok) ans++;
        }
    }
    return ans;
}

int main() {
    open['['] = 1;
    open['{'] = 1;
    open['('] = 1;
    close['['] = ']';
    close['('] = ')';
    close['{'] = '}';
    go2("{}");
    int n = 60;
    for (int i = 0; i < 10000; ++i) {
        string s;
        for (int j = 0; j < n; ++j)
            s += ("([{}])"[rand() % 6]);
        int a = go(s), b = go2(s);
        if (a != b) {
            cout << "!"; go2(s);
        }
    }
}