#include <iostream>
#include <stack>
#include <vector>

using namespace std;

int main() {
    int n;
    cin >> n;
    char emp;
    cin.get(emp);
    while(emp != '\n'){
        cin.get(emp);
    }
    // 读取括号序列
    string brackets;
    getline(cin, brackets);

    stack<char> stack1;  // 第一个栈，用于存储右括号
    stack<char> stack2;  // 第二个栈，用于存储未匹配的右括号

    // 从后向前遍历括号序列
    for (int i = n - 1; i >= 0; --i) {
        if (brackets[i] == ')' || brackets[i] == ']' || brackets[i] == '}') {
            stack1.push(brackets[i]);
        } else if (brackets[i] == '(' || brackets[i] == '[' || brackets[i] == '{') {
            char left = brackets[i];
            char right;
            if (left == '(') right = ')';
            else if (left == '[') right = ']';
            else if (left == '{') right = '}';

            int a = 1;  // 统计连续的左括号数量
            while (i > 0 && brackets[i - 1] == left) {
                a++;
                i--;
            }

            int b = 0;  // 统计栈顶连续的匹配的右括号数量
            while (!stack1.empty() && stack1.top() == right) {
                b++;
                stack1.pop();
            }

            if (a < b) {
                for(int j = 0; j < b - a; ++j){
                    stack1.push(right);
                }
                for(int j = 0; j < a / 2; ++j){
                    stack2.push(right);
                }
            } else if (a < 2 * b) {
                for (int j = 0; j < b - (a + 1) / 2; ++j) {
                    stack2.push(right);
                }
            } else if (a == 2 * b) {
                continue;
            } else if (a > 2 * b) {
                int remaining = a - 2 * b;
                while (remaining > 0 && !stack2.empty()) {
                    if (stack2.top() == right) {
                        stack2.pop();
                        remaining-=2;
                    } else {
                        stack2.pop();
                    }
                }
                if (remaining > 0) {
                    cout << 0 << endl;
                    return 0;
                }
            }
        }
    }

    if (stack1.empty()) {
        cout << 1 << endl;
    } else {
        cout << 0 << endl;
    }

    return 0;
}