zbk1Bq - Online IDE & Debugging Tool

process.stdin.resume();
process.stdin.setEncoding('utf8');

// your code goes here
function solve() {
  const input = require('fs').readFileSync('/dev/stdin', 'utf8').trim();
  const s = input;
  const n = s.length;

  if (n % 2 === 1) {
    console.log(0);
    return;
  }

  let openCount = 0;
  for (let i = 0; i < n; i++) {
    if (s[i] === '(') openCount++;
  }

  const target = n / 2;

  if (Math.abs(openCount - target) !== 1) {
    console.log(0);
    return;
  }

  const balance = new Array(n + 1).fill(0);
  for (let i = 0; i < n; i++) {
    balance[i + 1] = balance[i] + (s[i] === '(' ? 1 : -1);
  }

  const minBalanceFromStart = new Array(n + 1).fill(0);
  minBalanceFromStart[0] = balance[0];
  for (let i = 1; i <= n; i++) {
    minBalanceFromStart[i] = Math.min(balance[i], minBalanceFromStart[i - 1]);
  }

  const minBalanceToEnd = new Array(n + 2).fill(Infinity);
  minBalanceToEnd[n] = balance[n];
  for (let i = n - 1; i >= 0; i--) {
    minBalanceToEnd[i] = Math.min(balance[i], minBalanceToEnd[i + 1]);
  }

  let validFlips = 0;

  if (openCount === target + 1) {
    for (let i = 0; i < n; i++) {
      if (s[i] === '(') {
        if (minBalanceFromStart[i] >= 0 && minBalanceToEnd[i + 1] >= 2) {
          validFlips++;
        }
      }
    }
  }

  if (openCount === target - 1) {
    for (let i = 0; i < n; i++) {
      if (s[i] === ')') {
        if (minBalanceFromStart[i] >= 0 && minBalanceToEnd[i + 1] >= -2) {
          validFlips++;
        }
      }
    }
  }

  console.log(validFlips);
}

solve();