括号机器人小 I 收到了一条由四种括号组成的序列 s:`<>`、`{}`、`[]`、`()`。
序列中的括号只有两种身份:**开括号**(`<`、`{`、`[`、`(`)与**闭括号**(`>`、`}`、`]`、`)`)。机器人可以对任意一个括号做一次"替换"操作,但受硬件限制,**开括号只能替换成另一种开括号,闭括号只能替换成另一种闭括号**。例如:`<` 可以替换成 `{`,但不能替换成 `)` 或 `>`。
我们定义**合法括号序列(Regular Bracket Sequence)**如下:
1. 空序列是合法括号序列。
2. 若 s_1、s_2 均为合法括号序列,则 \langle s_1\rangle s_2、\{s_1\}s_2、[s_1]s_2、(s_1)s_2 也是合法括号序列。
例如 `[[(){}]<>]` 是合法括号序列,而 `[)()` 与 `][()()` 不是。
请你求出:最少需要替换多少个括号,才能把 s 变成一个合法括号序列。如果无论如何都无法做到,输出 `Impossible`。
一行一个非空字符串 s,仅由 `<>{}[]()` 这八种字符组成
若无法变成合法括号序列,输出 `Impossible`(注意首字母大写,其余小写)。
否则输出一个整数,表示最少的替换次数。
[<}){}
2
]]
Impossible
样例说明
样例 1:把第 1 个字符 `[` 替换成 `(`、第 2 个字符 `<` 替换成 `{`,得到 `({}){}`,是合法括号序列,共替换 2 次。样例 2:两个闭括号没有任何开括号与它们配对,永远无法修复。
| 20% | 1~5 | 20 | \lvert s\rvert \le 20 |
| 60% | 6~15 | 40(累计 60) | \lvert s\rvert \le 2000 |
| 100% | 16~25 | 40(累计 100) | \lvert s\rvert \le 10^6 |
对于全部数据,保证 1 \le |s| \le 10^6。
| 时间限制 | 1 秒 |
| 内存限制 | 128 MB |