有一棵二叉樹，根結(jié)點(diǎn)上有一個(gè)空字符串，每個(gè)點(diǎn)的左兒子上的字符串為其父親結(jié)點(diǎn)的字符串尾部額外加一個(gè)左括號，右兒子則是在尾部加一個(gè)右括號。樹中的每個(gè)葉子結(jié)點(diǎn)上的字符串都分別和每個(gè)由 n 對括號組成的合法括號序列一一對應(yīng)。

給定 n，求此時(shí)這棵樹的最大匹配所含的邊數(shù)。

9

10350

對于 20% 的評測用例，n ≤ 10 ；

對于 40% 的評測用例，n ≤ 300 ；

對于 60% 的評測用例，n ≤ 5000 ；

對于 85% 的評測用例，n ≤ 10⁵ ；

對于所有評測用例，1 ≤ n ≤ 10⁶ 。