K. Wahban and brackets
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Wahban is known for his admiration for bracket sequences, especially regular bracket sequences $$$\dagger$$$ One day, while playing ping-pong with his friend, Zaghloul, he found a weird piece of paper with the title "REVERSE" and below it a sequence of brackets, and after an intensive moment of thinking, his friend, Zaghloul, asked him if he could obtain a Reversed regular bracket sequence $$$\ast$$$ from the given sequence, Wahban took the problem personally and decided not only to solve the problem, but to print the maximum reversed regular brackets subsequence$$$\top$$$ size, help Wahabn solve the problem or report it's impossible.

$$$\dagger$$$A regular bracket sequence is a bracket sequence that can be transformed into a correct arithmetic expression by inserting the characters 1 and + between the original characters of the sequence, for example: () and ()(()) are valid, while ()) and )( are invalid

$$$\ast$$$ A sequence is called reverse bracket sequence if and only if when we reverse the whole string, it gives us Regular bracket sequence, )( is valid, while () and ()() are invalid

$$$\top$$$ Subsequence is bunch of indices that can be obtained from deleting zero or more indices from the start, end or even middle of any sequence, for example: given this sequence 1,2,3,4,5 one valid subsequence is 1,3,5. }

Input

The only input is string $$$S$$$ $$$(1 \le |S| \le 10^6)$$$

Output

if it's impossible to obtain any valid subsequence, output $$$-1$$$.

otherwise, output the maximum size of a such valid subsequence.

Examples
Input
()
Output
-1
Input
()()()
Output
4
Note

In test case 1, if we reverse the string () we get )(, which's not valid, so there's no valid answer.

In test case 2, looking at the string at indices 2,3 ")(", if we reversed we get a valid sequence () of size = 2, also string formed from indices 2,5 ")(" gives us the same answer, the maximum answer is obtained from the string with indices 2,3,4,5 ")()("