题目描述

给定长度为n的一个括号序列，每次修改可以修改一个位置的括号，若这个括号为’(‘，则修改为’)’，若这个括号为’)’，则修改为’(‘，问最少修改多少个使得原括号序列合法。 其中： 1、()是合法的； 2、若A是合法的，则(A)是合法的； 3、若A，B都是合法的，则AB是合法的。

输入

一个长度为n个括号的序列。

输出

最少的修改的次数。 如果修改后也无法实现完全匹配则输出“Impossible”。

样例输入

())(

样例输出

2

提示

样例说明 修改为()()，其中红色部分表示修改的括号。

数据范围 100%的数据满足：1 <= n <= 100,000。