PARENTHESES TS10 PTNK 2020-2021

#define task "PARENTHESES"

#include <iostream>
#include <cstdio>

using namespace std;

using ll = long long;
using ld = long double;

constexpr int N = 1e6 + 5;
constexpr int Inf = 1e9 + 7;
int n;
string s;
int b[N];
int pref[N], suf[N];

void Read()
{
    cin >> s;
    n = s.size();

    for (int i = 1; i <= n; ++i)
        b[i] = b[i - 1] + (s[i - 1] == '(' ? 1 : -1);
}

void Solve()
{
    if (b[n] != 0) // Không thể tạo ra dãy ngoặc đúng
    {
        cout << -1;
        return;
    }

    pref[0] = suf[n + 1] = Inf;

    for (int i = 1; i <= n; ++i)
        pref[i] = min(pref[i - 1], b[i]);
    for (int i = n; i; --i)
        suf[i] = min(suf[i + 1], b[i]);

    for (int i = 0; i < n; ++i)
        if (pref[i] >= b[i] - b[n] && suf[i + 1] >= b[i]) // Tìm thấy cách tạo dãy ngoặc đúng
        {
            cout << i;
            return;
        }
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if (fopen(task ".INP", "r"))
    {
        freopen(task ".INP", "r", stdin);
        freopen(task ".OUT", "w", stdout);
    }

    Read();
    Solve();
}