#include <stdio.h>
#include <vector>
#define INF 1000000007
char S[305];
std::vector<int> Xpos;
std::vector<char> ChangeBit;
typedef struct node node;
struct node
{
int v;
int sum, sumrev;
int mn, mnrev;
};
int N;
node Seg[1205];
int Fen[305];
int Q[305];
void up(int p, int v)
{
p++;
for (; p <= N; p += p&-p)
Fen[p] += v;
}
int qu(int p)
{
p++;
int r = 0;
for (; p > 0; p -= p&-p)
r += Fen[p];
return r;
}
int min(int a, int b)
{
return (a < b)?a:b;
}
int max(int a, int b)
{
return (a > b)?a:b;
}
void makeTree(int s, int e, int cell)
{
if (s == e)
{
Seg[cell].v = ((S[s] == '(')?1:-1);
Seg[cell].sum = Seg[cell].v;
Seg[cell].sumrev = -Seg[cell].v;
Seg[cell].mn = Seg[cell].v;
Seg[cell].mnrev = -Seg[cell].v;
return;
}
int m = (s + e)/2;
makeTree(s, m, 2*cell + 1);
makeTree(m + 1, e, 2*cell + 2);
Seg[cell].sum = Seg[2*cell + 1].sum + Seg[2*cell + 2].sum;
Seg[cell].sumrev = Seg[2*cell + 1].sumrev + Seg[2*cell + 2].sumrev;
Seg[cell].mn = min(Seg[2*cell + 1].mn, Seg[2*cell + 1].sum + Seg[2*cell + 2].mn);
Seg[cell].mnrev = min(Seg[2*cell + 1].mnrev, Seg[2*cell + 1].sumrev + Seg[2*cell + 2].mnrev);
}
void preprocess()
{
int i;
for (i = 0; i < N; i++)
{
up(i, ((S[i] == '(')?1:-1));
Q[i] = qu(i);
// printf("Q %d ", Q[i]);
}
makeTree(0, N - 1, 0);
}
void update(int p, int s, int e, int cell)
{
if (s == e)
{
// printf("update p = %c\n", S[s]);
Seg[cell].v = ((S[s] == '(')?1:-1);
Seg[cell].sum = Seg[cell].v;
Seg[cell].sumrev = -Seg[cell].v;
Seg[cell].mn = Seg[cell].v;
Seg[cell].mnrev = -Seg[cell].v;
return;
}
int m = (s + e)/2;
if (p <= m)
update(p, s, m, 2*cell + 1);
else
update(p, m + 1, e, 2*cell + 2);
Seg[cell].sum = Seg[2*cell + 1].sum + Seg[2*cell + 2].sum;
Seg[cell].sumrev = Seg[2*cell + 1].sumrev + Seg[2*cell + 2].sumrev;
Seg[cell].mn = min(Seg[2*cell + 1].mn, Seg[2*cell + 1].sum + Seg[2*cell + 2].mn);
Seg[cell].mnrev = min(Seg[2*cell + 1].mnrev, Seg[2*cell + 1].sumrev + Seg[2*cell + 2].mnrev);
}
void change(int i)
{
up(i, ((S[i] == '(')?2:-2));
update(i, 0, N - 1, 0);
for (; i < N; i++)
Q[i] = qu(i);
// for (i = 0; i < N; i++)
// printf("Q %d ", Q[i]);
}
node query(int qs, int qe, int s, int e, int cell)
{
// printf("query %d %d %d %d %d\n", qs, qe, s, e, cell);
if (qs == s && qe == e)
return Seg[cell];
int m = (s + e)/2;
node l = {INF, 0, 0, INF, INF};
node r = {INF, 0, 0, INF, INF};
if (qs <= m)
l = query(qs, min(m, qe), s, m, 2*cell + 1);
if (m + 1 <= qe)
r = query(max(m + 1, qs), qe, m + 1, e, 2*cell + 2);
node ret;
ret.sum = l.sum + r.sum;
ret.sumrev = l.sumrev + r.sumrev;
ret.mn = min(l.mn, l.sum + r.mn);
ret.mnrev = min(l.mnrev, l.sumrev + r.mnrev);
// printf("l %d %d %d %d\n", l.sum, l.sumrev, l.mn, l.mnrev);
// printf("r %d %d %d %d\n", r.sum, r.sumrev, r.mn, r.mnrev);
// printf("ret %d %d %d %d\n", ret.sum, ret.sumrev, ret.mn, ret.mnrev);
return ret;
}
int checkrange(int i, int j)
{
int mn = INF;
node p;
if (i > 0)
{
p = query(0, i - 1, 0, N - 1, 0);
mn = min(mn, p.mn);
// printf("{%d %d %d %d %d} mn %d\n", p.v, p.sum, p.sumrev, p.mn, p.mnrev, mn);
}
p = query(i, j, 0, N - 1, 0);
mn = min(mn, ((i > 0)?Q[i - 1]:0) + p.mnrev);
// printf("{%d %d %d %d %d} mn %d\n", p.v, p.sum, p.sumrev, p.mn, p.mnrev, mn);
if (j < N - 1)
{
p = query(j + 1, N - 1, 0, N - 1, 0);
mn = min(mn, 2*((i > 0)?Q[i - 1]:0) - Q[j] + p.mn);
// printf("{%d %d %d %d %d} mn %d\n", p.v, p.sum, p.sumrev, p.mn, p.mnrev, mn);
}
// printf("mn %d\n", mn);
return (mn == 0);
}
int check()
{
if (Q[N - 1]%2)
return 0;
else if (Q[N - 1] == 0 && query(0, N - 1, 0, N - 1, 0).mn == 0)
return 1;
int i, j, q;
std::vector<int> V[610];
V[N].push_back(-1);
for (i = 0; i < N; i++)
{
q = Q[i] - Q[N - 1]/2;
for (j = 0; j < V[q + N].size(); j++)
{
// printf("%d %d\n", V[q + N][j] + 1, i);
if (checkrange(V[q + N][j] + 1, i))
return 1;
}
V[Q[i] + N].push_back(i);
}
return 0;
}
void printTree(int s, int e, int cell)
{
if (s == e)
{
printf("(%d %d) %d %d %d %d %d\n", s, e, Seg[cell].v, Seg[cell].sum, Seg[cell].sumrev, Seg[cell].mn, Seg[cell].mnrev);
return;
}
int m = (s + e)/2;
printTree(s, m, 2*cell + 1);
printf("(%d %d) %d %d %d %d %d\n", s, e, Seg[cell].v, Seg[cell].sum, Seg[cell].sumrev, Seg[cell].mn, Seg[cell].mnrev);
printTree(m + 1, e, 2*cell + 2);
}
int main()
{
scanf("%d", &N);
int i, X = 0;
scanf("%s", S);
for (i = 0; i < N; i++)
{
if (S[i] == 'x')
{
Xpos.push_back(i);
X++;
S[i] = '(';
}
}
int j, s;
for (i = 0; i < X; i++)
{
ChangeBit.push_back(i);
s = ChangeBit.size();
for (j = 0; j < s - 1; j++)
ChangeBit.push_back(ChangeBit[j]);
}
int cnt = 0;
// printf("%s\n", S);
preprocess();
// printTree(0, N - 1, 0);
if (check())
cnt++;
for (i = 0; i < ChangeBit.size(); i++)
{
if (S[Xpos[ChangeBit[i]]] == '(')
S[Xpos[ChangeBit[i]]] = ')';
else
S[Xpos[ChangeBit[i]]] = '(';
// printf("%s\n", S);
change(Xpos[ChangeBit[i]]);
// printTree(0, N - 1, 0);
if (check())
cnt++;
}
printf("%d", cnt);
}
