有一棵二叉树，根结点上有一个空字符串，每个点的左儿子上的字符串为其父亲结点的字符串尾部额外加一个左括号，右儿子则是在尾部加一个右括号。树中的每个叶子结点上的字符串都分别和每个由 n 对括号组成的合法括号序列一一对应。
给定 n，求此时这棵树的最大匹配所含的边数。
9
10350
对于 20% 的评测用例，n ≤ 10 ；
对于 40% 的评测用例，n ≤ 300 ；
对于 60% 的评测用例，n ≤ 5000 ；
对于 85% 的评测用例，n ≤ 105 ；
对于所有评测用例，1 ≤ n ≤ 106 。