题目描述

给定一个长度为 $n$ 的字符串 $s$，字符串由 $(, ), [, ]$ 组成，问其中最长的合法子序列有多长？也就是说，我们要找到最大的 $m$，使得存在 $i_1,i_2,…,i_m$ 满足 $1≤i_1<i_2<⋯<i_m≤n$ 并且 $s_{i_1}s_{i_2}…s_{i_m}$ 是一个合法的括号序列。

合法的括号序列的定义是：

• $1$ 空串是一个合法的括号序列。
• $2$ 若 $A$ 是一个合法的括号序列，则 $(A), [A]$ 也是合法的括号序列。
• $3$ 若 $A, B$ 都是合法的括号序列，则 $AB$ 也是合法的括号序列。

输入格式

第一行一个整数 $n$。

接下来一行，一个长度为 $n$ 的字符串 $s$。

输出格式

一个数，表示答案。

Samples

10
]]][()]])[

4

数据规模

对于所有数据，保证 $1≤n≤500$。