Problem 24: Minimum Swaps for Bracket Sequence

Problem Statement: Given a string consisting of only '[' and ']', determine the minimum number of adjacent swaps required to balance the bracket sequence. It is guaranteed that a balanced arrangement exists.

Input

A single line containing a string of '[' and ']'.

Output

Print the minimum number of swaps needed.

Examples


Input:
]][][][[

Output:
2

Solution in C++


#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s; cin >> s;
    int n = s.size();
    vector<int> pos;
    for (int i = 0; i < n; i++) {
        if(s[i]=='[') pos.push_back(i);
    }
    int count = 0, p = 0, ans = 0;
    for(int i = 0; i < n; i++){
        if(s[i]=='[') {
            count++;
            p++;
        } else {
            count--;
        }
        if(count < 0){
            ans += pos[p] - i;
            swap(s[i], s[pos[p]]);
            p++;
            count = 1;
        }
    }
    cout << ans << "\n";
    return 0;
}