As Will is stuck in the Upside Down, he can still communicate with his mom, Joyce, through the Christmas lights (he can turn them on and off with his mind). He can't directly tell his mom where he is, because the monster that took him to the Upside Down will know and relocate him.  [Image] 

Thus, he came up with a puzzle to tell his mom his coordinates. His coordinates are the answer to the following problem.

A string consisting only of parentheses ('(' and ')') is called a bracket sequence. Some bracket sequence are called correct bracket sequences. More formally:  Empty string is a correct bracket sequence.  if s is a correct bracket sequence, then (s) is also a correct bracket sequence.  if s and t are correct bracket sequences, then st (concatenation of s and t) is also a correct bracket sequence. 

A string consisting of parentheses and question marks ('?') is called pretty if and only if there's a way to replace each question mark with either '(' or ')' such that the resulting string is a non-empty correct bracket sequence.

Will gave his mom a string s consisting of parentheses and question marks (using Morse code through the lights) and his coordinates are the number of pairs of integers (l, r) such that 1 ≤ l ≤ r ≤ |s| and the string s_{l}s_{l} + 1... s_{r} is pretty, where s_{i} is i-th character of s.

Joyce doesn't know anything about bracket sequences, so she asked for your help.


-----Input-----

The first and only line of input contains string s, consisting only of characters '(', ')' and '?' (2 ≤ |s| ≤ 5000).


-----Output-----

Print the answer to Will's puzzle in the first and only line of output.


-----Examples-----
Input
((?))

Output
4

Input
??()??

Output
7



-----Note-----

For the first sample testcase, the pretty substrings of s are:  "(?" which can be transformed to "()".  "?)" which can be transformed to "()".  "((?)" which can be transformed to "(())".  "(?))" which can be transformed to "(())".  

For the second sample testcase, the pretty substrings of s are:  "??" which can be transformed to "()".  "()".  "??()" which can be transformed to "()()".  "?()?" which can be transformed to "(())".  "??" which can be transformed to "()".  "()??" which can be transformed to "()()".  "??()??" which can be transformed to "()()()".

Difficulty: MEDIUM_HARD
Tags: Mathematics

Dynamic programming

Implementation

Greedy algorithms
Skill types: Dynamic programming

Greedy algorithms

Starter code:

Solutions:
st = input()
le = len(st)
ans = 0
for i in range(le):
	l = 0
	w = 0
	for j in range(i, le):
		if st[j] == '(':
			l += 1
		elif st[j] == ')':
			l -= 1
		else:
			w += 1
		if l + w < 0:
			break
		elif w > l:
			xx = l
			l = w
			w = xx
		elif l == w:
			ans += 1
print(ans)


s = input()
l = len(s)
ans = 0
for i in range(0, l):
	ln = n = 0
	for j in range(i, l):
		if s[j] == '(':
			ln += 1
		elif s[j] == ')':
			ln -= 1
		else:
			n += 1
			ln -= 1
		if ln == 0:
			ans += 1
		elif ln < 0:
			if n > 0:
				ln += 2
				n -= 1
			else:
				break
print(ans)


import sys
import math
from collections import defaultdict, deque
s = sys.stdin.readline()[:-1]
n = len(s)
dp = [[False for _ in range(n)] for x in range(n)]
left = [n for _ in range(n)]
ans = 0
for i in range(n - 1, -1, -1):
	right = i
	for j in range(i + 1, n):
		if j - i + 1 == 2:
			if (s[i] == '(' or s[i] == '?') and (s[j] == ')' or s[j] == '?'):
				dp[i][j] = True
				left[j] = min(left[j], i)
				right = j
				ans += 1
				continue
		if (j - i + 1) % 2 == 0:
			l = left[j]
			if dp[i][l - 1]:
				dp[i][j] = True
				left[j] = i
				right = j
				ans += 1
				continue
			if dp[right + 1][j]:
				dp[i][j] = True
				left[j] = i
				right = j
				ans += 1
				continue
			if (s[i] == '(' or s[i] == '?') and (s[j] == ')' or s[j] == '?'):
				if dp[i + 1][j - 1]:
					dp[i][j] = True
					left[j] = i
					right = j
					ans += 1
					continue
print(ans)


s = input()
a = 0
n = len(s)
for i in range(n):
	l = 0
	k = 0
	for j in range(i, n):
		l += s[j] == '('
		l -= s[j] == ')'
		k += s[j] == '?'
		if l + k < 0:
			break
		if k > l:
			(l, k) = (k, l)
		if l == k:
			a += 1
print(a)


s = input()
n = len(s)
res = 0
for i in range(n):
	(depth1, depth2) = (0, 0)
	for c in s[i:]:
		if c == '(':
			depth1 += 1
			depth2 += 1
		elif c == ')':
			depth1 -= 1
			depth2 -= 1
		else:
			depth1 += 1
			depth2 -= 1
		if depth1 < 0:
			break
		depth2 = max(depth2, 0)
		if depth1 & 1 == 0 and depth2 == 0:
			res += 1
print(res)


s = input().strip()
n = len(s)
ques = ans = ini = 0
for i in range(n):
	ques = ini = 0
	for j in range(i, n):
		c = s[j]
		if c == '?':
			ques += 1
		elif c == '(':
			ini += 1
		else:
			ini -= 1
		if ini < 0:
			break
		if ques > ini:
			ques -= 1
			ini += 1
		if (j - i + 1) % 2 == 0 and ques == ini:
			ans += 1
print(ans)


import sys
li = lambda : [int(x) for x in sys.stdin.readline().strip().split()]
rw = lambda : sys.stdin.readline().strip().split()
ni = lambda : int(sys.stdin.readline().strip())
nsi = lambda : sys.stdin.readline().strip()
from collections import defaultdict as df
from math import *
s = nsi()
n = len(s)
ans = 0
for i in range(n):
	l = 0
	r = 0
	for j in range(i, n):
		if s[j] == '(':
			l += 1
			r += 1
		elif s[j] == ')':
			l -= 1
			r -= 1
		else:
			l -= 1
			r += 1
		if l < 0:
			l += 2
		if r < 0:
			break
		if l == 0:
			ans += 1
print(ans)


s = str(input())
n = len(s)
ans = 0
dp = [[0 for _ in range(n)] for _ in range(2)]
for i in range(n - 1):
	if s[i] == ')':
		continue
	dp[0][i] = 1
	dp[1][i] = 1
	for j in range(i + 1, n):
		if s[j] == '(':
			dp[0][j] = dp[0][j - 1] + 1
			dp[1][j] = dp[1][j - 1] + 1
		elif s[j] == '?':
			dp[0][j] = dp[0][j - 1] + 1
			dp[1][j] = max(dp[1][j - 1] - 1, 0)
		elif s[j] == ')' and 0 < dp[0][j - 1]:
			dp[0][j] = dp[0][j - 1] - 1
			dp[1][j] = max(dp[1][j - 1] - 1, 0)
		else:
			break
		if (j - i) % 2 == 1 and dp[1][j] == 0:
			ans += 1
print(ans)


s = input()
n = len(s)
f = [[0 for i in range(n)] for j in range(n)]
g = [[0 for i in range(n)] for j in range(n)]
for l in range(n):
	count = 0
	for r in range(l, n):
		if s[r] == '(' or s[r] == '?':
			count += 1
		else:
			count -= 1
		if count < 0:
			break
		else:
			f[l][r] = 1
for r in range(n):
	count = 0
	for l in range(r, -1, -1):
		if s[l] == ')' or s[l] == '?':
			count += 1
		else:
			count -= 1
		if count < 0:
			break
		else:
			g[l][r] = 1
cnt = 0
for l in range(n):
	for r in range(l, n):
		if f[l][r] == 1 and g[l][r] == 1 and ((r - l) % 2 == 1):
			cnt += 1
print(cnt)


s = str(input())
n = len(s)
ans = 0
for l in range(n - 1):
	cnt = 0
	qu = 0
	chk = 0
	if s[l] == '(':
		cnt += 1
		chk += 1
	elif s[l] == '?':
		qu += 1
		chk = max(chk - 1, 0)
	else:
		continue
	for r in range(l + 1, n):
		if s[r] == '(':
			cnt += 1
			chk += 1
		elif s[r] == '?':
			qu += 1
			chk = max(chk - 1, 0)
		else:
			cnt -= 1
			chk = max(chk - 1, 0)
		if cnt + qu < 0:
			break
		elif (qu - cnt) % 2 == 0 and qu - cnt >= 0 and ((qu - cnt) // 2 <= qu) and (chk <= 0):
			ans += 1
print(ans)


def main():
	s = input()
	l = len(s)
	pretty_count = 0
	for i in range(l):
		left_paren_count = 0
		right_paren_count = 0
		wild_count = 0
		for j in range(i, l):
			if s[j] == '(':
				left_paren_count += 1
			elif s[j] == ')':
				right_paren_count += 1
			else:
				wild_count += 1
			if left_paren_count + wild_count < right_paren_count:
				break
			if left_paren_count < wild_count + right_paren_count:
				wild_count -= 1
				left_paren_count += 1
				if wild_count < 0:
					break
			if left_paren_count == wild_count + right_paren_count:
				pretty_count += 1
	print(pretty_count)
main()


from sys import stdin, stdout
from math import gcd, sqrt, factorial, pi, inf
from collections import deque, defaultdict
from bisect import bisect, bisect_left
from time import time
from itertools import permutations as per
from heapq import heapify, heappush, heappop, heappushpop
input = stdin.readline
R = lambda : map(int, input().split())
I = lambda : int(input())
S = lambda : input().rstrip('\r\n')
L = lambda : list(R())
P = lambda x: stdout.write(str(x) + '\n')
lcm = lambda x, y: x * y // gcd(x, y)
nCr = lambda x, y: f[x] * inv(f[y] * f[x - y] % N) % N
inv = lambda x: pow(x, N - 2, N)
sm = lambda x: (x ** 2 + x) // 2
N = 10 ** 9 + 7
s = S()
n = len(s)
i = 0
ans = 0
while i < n:
	j = i
	x = 0
	y = 0
	z = 0
	while j < n and y <= j - i >> 1:
		if s[j] == '(':
			x += 1
			z += 1
		elif s[j] == ')':
			y += 1
		if s[j] != '(' and z:
			z -= 1
		if j != i and j - i & 1 and (j - i + 1 >> 1 >= x) and (not z):
			ans += 1
		j += 1
	i += 1
print(ans)


import os
import sys
import math
from io import BytesIO, IOBase
import io
from fractions import Fraction
import collections
from itertools import permutations
from collections import defaultdict
from collections import deque
import threading
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class SegmentTree:

	def __init__(self, data, default=0, func=lambda a, b: a + b):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class SegmentTree1:

	def __init__(self, data, default=10 ** 6, func=lambda a, b: min(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)
MOD = 10 ** 9 + 7

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD
mod = 10 ** 9 + 7
omod = 998244353

class LazySegTree:

	def __init__(self, _op, _e, _mapping, _composition, _id, v):

		def set(p, x):
			assert 0 <= p < _n
			p += _size
			for i in range(_log, 0, -1):
				_push(p >> i)
			_d[p] = x
			for i in range(1, _log + 1):
				_update(p >> i)

		def get(p):
			assert 0 <= p < _n
			p += _size
			for i in range(_log, 0, -1):
				_push(p >> i)
			return _d[p]

		def prod(l, r):
			assert 0 <= l <= r <= _n
			if l == r:
				return _e
			l += _size
			r += _size
			for i in range(_log, 0, -1):
				if l >> i << i != l:
					_push(l >> i)
				if r >> i << i != r:
					_push(r >> i)
			sml = _e
			smr = _e
			while l < r:
				if l & 1:
					sml = _op(sml, _d[l])
					l += 1
				if r & 1:
					r -= 1
					smr = _op(_d[r], smr)
				l >>= 1
				r >>= 1
			return _op(sml, smr)

		def apply(l, r, f):
			assert 0 <= l <= r <= _n
			if l == r:
				return
			l += _size
			r += _size
			for i in range(_log, 0, -1):
				if l >> i << i != l:
					_push(l >> i)
				if r >> i << i != r:
					_push(r - 1 >> i)
			l2 = l
			r2 = r
			while l < r:
				if l & 1:
					_all_apply(l, f)
					l += 1
				if r & 1:
					r -= 1
					_all_apply(r, f)
				l >>= 1
				r >>= 1
			l = l2
			r = r2
			for i in range(1, _log + 1):
				if l >> i << i != l:
					_update(l >> i)
				if r >> i << i != r:
					_update(r - 1 >> i)

		def _update(k):
			_d[k] = _op(_d[2 * k], _d[2 * k + 1])

		def _all_apply(k, f):
			_d[k] = _mapping(f, _d[k])
			if k < _size:
				_lz[k] = _composition(f, _lz[k])

		def _push(k):
			_all_apply(2 * k, _lz[k])
			_all_apply(2 * k + 1, _lz[k])
			_lz[k] = _id
		_n = len(v)
		_log = _n.bit_length()
		_size = 1 << _log
		_d = [_e] * (2 * _size)
		_lz = [_id] * _size
		for i in range(_n):
			_d[_size + i] = v[i]
		for i in range(_size - 1, 0, -1):
			_update(i)
		self.set = set
		self.get = get
		self.prod = prod
		self.apply = apply
MIL = 1 << 20

def makeNode(total, count):
	return total * MIL + count

def getTotal(node):
	return math.floor(node / MIL)

def getCount(node):
	return node - getTotal(node) * MIL
nodeIdentity = makeNode(0.0, 0.0)

def nodeOp(node1, node2):
	return node1 + node2
	return makeNode(getTotal(node1) + getTotal(node2), getCount(node1) + getCount(node2))
identityMapping = -1

def mapping(tag, node):
	if tag == identityMapping:
		return node
	count = getCount(node)
	return makeNode(tag * count, count)

def composition(mapping1, mapping2):
	return mapping1 if mapping1 != identityMapping else mapping2
prime = [True for i in range(10)]
pp = [0] * 10

def SieveOfEratosthenes(n=10):
	p = 2
	c = 0
	while p * p <= n:
		if prime[p] == True:
			c += 1
			for i in range(p, n + 1, p):
				pp[i] += 1
				prime[i] = False
		p += 1

def binarySearch(arr, n, key):
	left = 0
	right = n - 1
	mid = 0
	res = arr[n - 1]
	while left <= right:
		mid = (right + left) // 2
		if arr[mid] >= key:
			res = arr[mid]
			right = mid - 1
		else:
			left = mid + 1
	return res

def binarySearch1(arr, n, key):
	left = 0
	right = n - 1
	mid = 0
	res = arr[0]
	while left <= right:
		mid = (right + left) // 2
		if arr[mid] > key:
			right = mid - 1
		else:
			res = arr[mid]
			left = mid + 1
	return res
s = input()
a = 0
l = len(s)
for i in range(l):
	k = 0
	m = 0
	for j in range(i, l):
		m += s[j] == '('
		m -= s[j] == ')'
		k += s[j] == '?'
		if m + k < 0:
			break
		if k > m:
			(m, k) = (k, m)
		if m == k:
			a = a + 1
print(a)


import sys
import math
input = sys.stdin.readline
from functools import cmp_to_key

def pi():
	return int(input())

def pl():
	return int(input(), 16)

def ti():
	return list(map(int, input().split()))

def ts():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
mod = 998244353
f = []

def fact(n, m):
	global f
	f = [1 for i in range(n + 1)]
	f[0] = 1
	for i in range(1, n + 1):
		f[i] = f[i - 1] * i % m

def fast_mod_exp(a, b, m):
	res = 1
	while b > 0:
		if b & 1:
			res = res * a % m
		a = a * a % m
		b = b >> 1
	return res

def inverseMod(n, m):
	return fast_mod_exp(n, m - 2, m)

def ncr(n, r, m):
	if r == 0:
		return 1
	return f[n] * inverseMod(f[n - r], m) % m * inverseMod(f[r], m) % m

def main():
	A()

def D():
	[n, m, k] = ti()
	w = [[] for i in range(n)]
	for i in range(n):
		w[i] = ts()
	mn = [[0 for j in range(k + 1)] for i in range(n + 1)]
	for i in range(1, n + 1):
		for j in range(k + 1):
			c = 0
			(st, en) = (-1, -1)
			for x in range(m):
				if w[i - 1][x] == '1':
					if c == j and st == -1:
						st = x
					if c < j:
						c += 1
					if c == j:
						en = x
			mn[i][j] = en - st + 1 if st != -1 and en != -1 else 0
			(st, en) = (-1, -1)
			c = 0
			for x in range(m - 1, -1, -1):
				if w[i - 1][x] == '1':
					if c == j and st == -1:
						st = x
					if c < j:
						c += 1
					if c == j:
						en = x
			if st != -1 and en != -1 >= 0:
				mn[i][j] = min(mn[i][j], st - en + 1)
	dp = [[9999999999999999 for j in range(k + 1)] for i in range(n + 1)]
	for i in range(k + 1):
		dp[0][i] = 0
	for i in range(1, n + 1):
		for j in range(k + 1):
			for x in range(k + 1):
				if j - x >= 0:
					dp[i][j] = min(dp[i][j], dp[i - 1][j - x] + mn[i][x])
	print(dp[n][k])

def A():
	s = ts()
	ans = 0
	for i in range(len(s)):
		(c, cq) = (0, 0)
		for j in range(i, len(s)):
			if s[j] == '(':
				c += 1
			if s[j] == ')':
				c -= 1
			if s[j] == '?':
				cq += 1
			while cq > 0 and cq > c:
				cq -= 1
				c += 1
			if c < 0:
				break
			if (c + cq) % 2 != 0:
				continue
			if c == cq:
				ans += 1
	print(ans)
main()


S = input()
n = len(S)
Ans = 0
for l in range(0, n):
	bs = 0
	det = 0
	for r in range(l, n):
		if S[r] == '?':
			if bs > 0:
				det = det + 1
				bs = bs - 1
			else:
				bs = bs + 1
		elif S[r] == '(':
			bs = bs + 1
		else:
			if bs == 0 and det > 0:
				bs = bs + 2
				det = det - 1
			bs = bs - 1
		if bs < 0:
			break
		if bs > 0:
			continue
		if bs % 2 == 0:
			Ans = Ans + 1
print(Ans)


s = input()
n = len(s)
res = 0
for st in range(n):
	(l, r) = (0, 0)
	for e in range(st, n):
		if s[e] == '(':
			l += 1
			r += 1
		elif s[e] == ')':
			l -= 1
			r -= 1
		elif s[e] == '?':
			l -= 1
			r += 1
		if r < 0:
			break
		if l < 0:
			l += 2
		if (e - st + 1) % 2 == 0 and (l <= 0 and 0 <= r) and (abs(l) % 2 == 0):
			res += 1
print(res)


s = input()
l = len(s)
ans = 0
for i in range(0, l):
	m = n = 0
	for j in range(i, l):
		m += s[j] == '('
		m -= s[j] == ')'
		n += s[j] == '?'
		if m + n < 0:
			break
		if m < n:
			(m, n) = (n, m)
		ans += m == n
print(ans)


s = input()
(res, n) = (0, len(s))
for i in range(n - 1):
	(j, c, q) = (i, 0, 0)
	while j < n and c + q >= 0:
		if s[j] == '(':
			c += 1
		elif s[j] == ')':
			c -= 1
		else:
			q += 1
		if c < q:
			(c, q) = (q, c)
		res += c == q
		j += 1
print(res)


s = input()
(res, n) = (0, len(s))
for i in range(n - 1):
	(cur, q, ind) = (0, 0, i)
	while ind < n:
		if s[ind] == '(':
			cur += 1
		elif s[ind] == ')':
			cur -= 1
		else:
			q += 1
		if cur + q < 0:
			break
		if q > cur:
			(cur, q) = (q, cur)
		res += cur == q
		ind += 1
print(res)


import sys, math, os.path
FILE_INPUT = 'c.in'
DEBUG = os.path.isfile(FILE_INPUT)
if DEBUG:
	sys.stdin = open(FILE_INPUT)

def ni():
	return int(input())

def nvi():
	return map(int, input().split(' '))

def nia():
	return list(map(int, input().split()))

def log(x):
	if DEBUG:
		print(x)
s = input()
ls = len(s)
count = 0
for i in range(0, ls):
	low = 0
	high = 0
	if s[i] != ')':
		for j in range(i, ls):
			if s[j] == '(':
				low += 1
				high += 1
			elif s[j] == ')':
				low = max(0, low - 1)
				high -= 1
			else:
				low = max(0, low - 1)
				high += 1
			if low > high:
				break
			if low <= 0 <= high and (j - i) % 2 == 1:
				count += 1
print(count)


s = input()
ans = 0
for i in range(0, len(s) - 1):
	addQ = 0
	subQ = 0
	cur = 0
	for j in range(i, len(s)):
		if s[j] == '(':
			cur += 1
		elif s[j] == ')':
			cur -= 1
			if cur < 0 and subQ > 0:
				cur += 2
				subQ -= 1
				addQ += 1
		elif cur > 0:
			subQ += 1
			cur -= 1
		else:
			addQ += 1
			cur += 1
		if cur < 0:
			break
		if cur == 0:
			ans += 1
print(ans)