You are given a string s consisting only of the characters ( and ).

In one reversal you may flip any single character: ( becomes ) or ) becomes (.

Return the minimum number of reversals needed to make s balanced (every opening bracket has a matching closing bracket after it, in the usual sense). If s is already balanced, return 0. If no sequence of reversals can balance s, return -1.

Examples

Example 1

Input: s = ")("
Output: 2
Explanation: Both characters must flip: ")(" -> "()".

Example 2

Input: s = "(()("
Output: 1
Explanation: Flipping the last character gives "(())".

Example 3

Input: s = "((("
Output: -1
Explanation: No sequence of flips turns "(((" into a balanced string.