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 Explanation

Method 1: Record the positions of vowels and then choose a target segment where the vowels are contiguous. Calculate the cost by summing the distances between current positions and target positions. Method 2: Use a sliding window approach on the array of vowel positions to minimize total swaps required.

Solution in C++


#include 
#include 
#include 
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 pos;
    for (int i=0; i