Problem 23: Minimum Adjacent Swaps to Group All Vowels

Problem Statement: Given a string, find the minimum number of adjacent swaps required to group all the vowels together. Only the positions of vowels matter.

Input

A single line containing the string (consisting of lowercase English letters).

Output

Print the minimum number of adjacent swaps needed.

Examples


Input:
abcdaeieo


Output:
5

Solution in C++


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

bool isVowel(char c) {
    return c=='a' || c=='e' || c=='i' || c=='o' || c=='u';
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s; getline(cin, s);
    vector<int> pos;
    for (int i=0; i<s.size(); i++) {
        if(isVowel(s[i])) pos.push_back(i);
    }
    if(pos.empty()){
        cout << 0 << "\n";
        return 0;
    }
    int m = pos.size();
    int mid = m/2;
    long long ans = 0;
    for(int i=0; i<m; i++){
        ans += abs(pos[i] - pos[mid] - (i - mid));
    }
    cout << ans << "\n";
    return 0;
}