今天是世界水日，著名的水题资源专家蝈蝈大臣发起了水题走四方活动，向全世界发放成千上万的水题。

蝈蝈大臣是家里蹲大学的教授，当然不愿意出门发水题啦！所以他委托他的助手欧姆来发。

助手欧姆最近做 UR #6 被狗狗传染了懒癌，当然不愿意出门发水题啦！所以他请来了高手 —— 地卜师。

全世界一共 $n$ 个城市，编号分别为 $1,\dots ,n$。城市之间由双向道路相连，形成了一棵树。如果这棵树以 $1$ 为根，则除 $1$ 以外每个结点 $v$ 的父亲结点的编号 $p_v$ 满足 $p_v<v$。

由于地卜师掌握了克隆的核心科技，把自己完全复制了一份，他和他的分身一共两个地卜师一起出去执行任务。

现在，两个地卜师都站在 $1$ 号城市。地卜师可以沿道路行走，从一个城市移动到另一个城市。走一条道路需要耗时 $1$ 小时。当然，地卜师可以停留在某个城市不动。每到一个没有发放水题的城市，地卜师都会发水题。在一个城市里发水题的时间不计。

由于地卜师有强迫症，他沿道路移动时总是从一个城市移动到编号更大的城市。即总是从一个结点移动到它的儿子结点。地卜师和他的分身可以同时移动。

但是地卜师这样好像不一定能经过所有的城市？没关系！地卜师会瞬移。如果某个时刻两个地卜师都在某个城市里（而不是在去某个城市的道路上），那么其中一个地卜师可以瞬移到另一个地卜师所在的城市。瞬移所需的时间不计。

现在地卜师想知道，要想顺利给每个城市都发放水题，最短需要多少个小时。

欧姆当然知道怎么计算啦！但是他想考考你。

输入格式

由于本题数据范围太大，为了方便读入，输入的是这棵树的括号序列表示。

第一行一个正整数 $n$。

第二行一个长度为 $2n$ 的字符串，仅包含 “(” 和 “)”。

下面给出了源代码，演示了怎样通过给出的括号序列求出每个结点的父亲。计算出了数组 p，p[v] 的值即为结点 $v$ 的父亲的编号（特别地，p[1] 为 $0$）。你可以直接照抄。

C/C++ 代码

scanf("%d", &n);
scanf("%s", s);
v = 0;
tot = 0;
for (i = 0; i < n * 2; i++)
{
    if (s[i] == '(')
    {
        tot++;
        p[tot] = v;
        v = tot;
    }
    else
        v = p[v];
}

Pascal

readln(n);
readln(s);
v := 0;
tot := 0;
for i := 1 to n * 2 do
begin
    if s[i] = '(' then
    begin
        inc(tot);
        p[tot] := v;
        v := tot;
    end
    else
        v := p[v];
end;

输出格式

一行一个整数，表示最短需要多少时间完成任务，以小时为单位。

样例一

input

7
((()())(())())

output

4

explanation

计算可得：p[1] = 0, p[2] = 1, p[3] = 2, p[4] = 2, p[5] = 1, p[6] = 5, p[7] = 1。

初始时两个地卜师都在 $1$，然后一个留在 $1$，另一个去 $5$ 号点 再去 $6$ 号点耗时 $2$ 小时，再瞬移回 $1$。然后两个地卜师一个去 $2$ 一个去 $7$，耗时 $1$ 小时，接着去 $7$ 的地卜师瞬移回 $2$，接着两个地卜师一个去 $3$ 一个去 $4$，耗时 $1$ 小时，共计 $4$ 小时。

样例二

input

1
()

output

0

样例三

见样例数据下载。

限制与约定

由于一些原因，本题使用捆绑测试。每个子任务有若干个测试点，分为 $4$ 个子任务，你只有通过一个子任务的所有测试点才能得到这个子任务的分数。

由于后一个子任务的数据范围总是包括了前一个子任务的数据范围，所以如果前一个子任务的测试点没有全部通过，后面的子任务都会被跳过并计后面的子任务 $0$ 分。

（骗分的小朋友考虑下造数据的人的感受好吗 TAT……）

时间限制：$1\mathtt{\text{s}}$

空间限制：$512\mathtt{\text{MB}}$

下载

样例数据下载