class ParenthesesDiv1Hard {
 public:
  template <class It>
  void parse(It b, It e, int root, vi* parent) {
    if (b == e) {
      return;
    }
    int sum = 1;
    ++b;
    int v = parent->size();
    parent->push_back(root);
    It s = b;
    while (sum) {
      if (*b == '(') {
        ++sum;
      } else {
        --sum;
      }
      ++b;
    }
    parse(b, e, root, parent);
    parse(s, prev(b), v, parent);
  }

  map<int, int> depth;

  int dfs(int r, const vii& al) {
    depth[r] = 1;
    for (int v2 : al[r]) {
      depth[r] = max(depth[r], 1 + dfs(v2, al));
    }
    return depth[r];
  }

  int cost(int r, const vii& al) {
    int res = 0;
    res += depth[r] * depth[r];
    for (int v2 : al[r]) {
      res += cost(v2, al);
    }
    return res;
  }

  int minCost(string s) {
    int sum = 0;
    for (int i = 0; i < s.size(); ++i) {
      if (s[i] == '(') {
        ++sum;
      } else {
        --sum;
      }
      if (sum < 0) {
        return -1;
      }
    }
    if (sum) {
      return -1;
    }
    vi parent;
    parse(s.begin(), s.end(), -1, &parent);

    vii al(parent.size());
    vi roots;
    for (size_t v = 0; v < parent.size(); ++v) {
      int p = parent[v];
      if (p == -1) {
        roots.push_back(v);
        continue;
      }
      p = parent[p];
      if (p == -1) {
        roots.push_back(v);
        continue;
      }
      al[p].push_back(v);
    }

    for (int r : roots) {
      dfs(r, al);
    }

    int res = 0;
    for (int r : roots) {
      res += cost(r, al);
    }

    return res;
  }
};