#include <bits/stdc++.h>
#define fread freopen("input.txt", "r", stdin);
#define fwrite freopen("output.txt", "w", stdout);
#define endl "\n"
#define F first
#define vi vector<int>
#define vl vector<long>
#define vll vector<long long>
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define SQ(a) (a) * (a)
#define REP(i, a, b) for (int i = a; i <= b; i++)
typedef long long ll;

using namespace std;

int maxSumSubArr(int n, int arr[]); // Kadane => O(N)
void processSubset();
void genSubsets(int n);
void genSubsetsRecursive(int k, int n);

// Calculates Operator precedence with respect to other operators
int getPrec(char oprtr) {
    // Operators => *,/,%,+,-,&,^,| (all are left to right associative)
    switch (oprtr) {
        // Multiplication, Division, Modulus
        case '*':
        case '/':
        case '%':
            return 5; // max precedence

        // Addition, Subtraction
        case '+':
        case '-':
            return 4;

        // Bitwise AND
        case '&':
            return 3;

        // Bitwise XOR
        case '^':
            return 2;

        // Bitwise OR
        case '|':
            return 1; // base (min precedence)

        // Unrecognised operator
        default:
            return -1;
    }
}

// Checks if character represents a closing parenthesis
bool isOpeningBracket(char exp) {
    return (exp == '{' || exp == '(' || exp == '[') ? true : false;
}

// Checks if character represents a closing parenthesis
bool isClosingBracket(char exp) {
    return (exp == '}' || exp == ')' || exp == ']') ? true : false;
}

// Checks for Precedence of operator1 with respect to operator2
bool hasHigherPrec(char oper1, char oper2) {
    // If operator1 has higher precendence, return true else false
   return ((getPrec(oper1) > getPrec(oper2)) ? true: false);
}

// Checks if string is operatpr or not
bool isOperator(char token) {
    // Checks for +,-,*,/,%,^,&,| operators
    if (token == '+' || token == '-' || token == '*' || token == '/' 
        || token == '%' || token == '^' || token == '&' || token == '|')
        return true; // Operator
    
    // Not operator
    return false;
}

// Perform a mathematical operation (opr) between two integrer operands and return result
int performOperation(int op1, int op2, string opr) {
    // Addition
    if (opr == "+")
        return op1 + op2;
    // Subtraction
    else if (opr == "-")
        return op1 - op2;
    // Division (returns floor for float result)
    else if (opr == "/")
        return op1 / op2;
    // Multiplication
    else if (opr == "*")
        return op1 * op2;
    // Modulus
    else if (opr == "%")
        return op1 % op2;
    // Bitwise OR
    else if (opr == "|")
        return op1 | op2;
    // Bitwise XOR
    else if (opr == "^")
        return op1 ^ op2;
    // Bitwise AND
    else if (opr == "&")
        return op1 & op2;
    // Unrecognized operation
    return -1;
}


// Conversion of infix expression to postfix expression
string infixToPostfix(int exp_len, string infix_exp) {
    string postfix_exp = ""; // initialise an empty string for resultant postfix expression
    stack <char> stack; // initialise and empty stack 
    
    
    // While not reached end of expression read through each token
    int i = 0;
    char token = infix_exp[i]; 
	while (token) 
    {
        // Any expression in brackets is considered as whole and operator precedence not checked with elements outside bracket

        // If token is an operator
        if (isOperator(token)) {
            // While operators in stack with higher precedence that token and we do not encounter an opening brace in Stack
            while(!stack.empty() && hasHigherPrec(stack.top(), token) && !isOpeningBracket(stack.top())) {
                // Pop the operator from stack and append to resultant postfix expression
                postfix_exp += stack.top();
				stack.pop();
            }
            // Once no operator with higher precedence in stack than token => push token to stack
            stack.push(token);
        } 
        
        // If token is an opening parenthesis => push onto stack
        else if (isOpeningBracket(token)) {
            stack.push(token);
        } 
        
        // If token is closing parenthesis
        else if (isClosingBracket(token)) {
            // While not opening parenthesis of token encountered
            while(!stack.empty() && !isOpeningBracket(stack.top())) {
                // Pop the operators from stack and append to resultant postfix expression
                postfix_exp += stack.top();
				stack.pop();
            }
            // Pop the final opening parenthesis of token from stack (not included in postfix expression)
            stack.pop();
        }

        // If token is an operand
        else {
            // Append the token to resultant postfix expression
            postfix_exp += token;
        } 

        // If end of expression => update token as NULL
        i++;
		token = infix_exp[i]; 
    }

    // If operators left in stack after end of infix expression
    while(!stack.empty()) {
        // Pop the operators from stack and append to resultant postfix expression
        postfix_exp += stack.top();
		stack.pop();
    }

    // Return resultant postfix expression
    return postfix_exp;
}

void solve()
{
    ll len, ind = 0, cnt = 0, ans = 0;
    string s;
    cin >> len >> s;
    ll sheeps = 0;
    for(auto x: s)
        if(x == '*')
            sheeps++;
    sheeps = (sheeps+1)/2;
    REP(i, 0, len-1) {
        if(s[i] == '*') {
            cnt++;
            if(cnt == sheeps) {
                ind = i;
                break;
            }
        }
    }
    cnt = 0;
    for(int j = ind-1; j >= 0; j--) {
        if(s[j] == '.')
            cnt++;
        else
            ans += cnt;
    }
    cnt = 0;
    for(int j = ind+1; j < len; j++) {
        if(s[j] == '.')
            cnt++;
        else
            ans += cnt;    
    }
    cout << ans << endl;
}


int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int tc;
	cin >> tc;
	while (tc--)
	{
	solve();
	}
}

/*
bool ready[int(1e5)];
int value[int(1e5)];
int minCoinForSumRecursive(int x, vi coins)
{
	if (x < 0)
		return INT_MAX;
	if (x == 0)
		return 0;
	if (ready[x])
		return value[x];

	int best = INT_MAX;
	for (auto c : coins)
		best = min(best, minCoinForSum(x - c) + 1);

	value[x] = best;
	ready[x] = true;

	return best;
}*/

/*
void nQueens(int y)
{
	if (y == n)
	{
		count++;
		return;
	}
	for (int x = 0; x < n; x++)
	{
		if (column[x] || diag1[x + y] || diag2[x - y + n - 1])
			continue;
		column[x] = diag1[x + y] = diag2[x - y + n - 1] = 1;
		nQueens(y + 1);
		column[x] = diag1[x + y] = diag2[x - y + n - 1] = 0;
	}
}
*/
// Only change this and call genSubsets(n)
void processSubset(vi v)
{
	for (auto x : v)
		cout << x << " ";
	cout << endl;
}

// Subsets of numbers => 0...n (FOR 2 =>  {}, {1}, {2}, {1,2})
void genSubsets(int n)
{
	for (int b = 0; b < (1 << n); b++)
	{
		vi subset;
		REP(i, 0, n - 1)
		{
			if (b & (1 << i))
				subset.push_back(i);
		}
		// HERE PROCESS SUBSET (USING SUBSET VECTOR)
		processSubset(subset);
	}
}

// Subsets of numbers => 0...n (FOR 2 =>  {}, {1}, {2}, {1,2})
/* vi subset;
void genSubsetsRecursive(int k, int n) // CALL => genSubsetsRecurive(0, n)
{
	if (k == n)
	{
		// HERE PROCESS SUBSET (USING SUBSET VECTOR)
	}
	else
	{
		genSubsetsRecursive(k + 1, n);
		subset.push_back(k);
		genSubsetsRecursive(k + 1, n);
		subset.pop_back();
	}
}
*/

int maxSumSubArr(int n, int arr[])
{
	// 0 size subarray allowed => max_sum >= 0
	int max_sum = 0, cur_sum = 0;
	REP(i, 0, n - 1)
	{
		cur_sum = max(arr[i], cur_sum + arr[i]);
		max_sum = max(max_sum, cur_sum);
	}

	return max_sum;
}

/*

COMMON METHODS
push pair<int, int> in vector => v.push_back({x,y}) OR v.push_back(make_pair(x,y))
push tuple<int, int, int> in vector => v.push_back({x,y,z}) OR v.push_back(make_tuple(x,y,z))
sort arr = sort(arr, arr+len) // can take third argument as comparison operator to be used for sorting (bool)
sort vector = sort(v.begin(), v.end()) (FOR PAIRS/TUPLE ON BASIS OF FIRST ITEM, IF SAME THEN SECOND AND SO ON)
sort vector rev = sort(v.rbegin(), v.rend()) 
reverse(v.begin(), v.end()) OR reverse(a, a+n) // reverse
random_shuffle(v.begin(), v.end()) OR random_shuffle(a, a+n) // shuffle

BINARY SEARCH (ONLY FOR SORTED ARRAYS)
lower_bound(arr, arr+len, x) => pointer to first item with value >=x
upper_bound(arr, arr+len, x) => pointer to first item with value >x
equal_range(arr, arr+len, x) => Pair of lower_bound(.first) and upper_bound pointer(.second)

auto k = lower_bound(arr, arr+n, x)-arr; // bin search equiv
if (k < n && array[k] == x) // x found at index k else x not present

Frequency of x in arr (difference b/w upper_bound and lower_bound => b-a OR r.second-r.first)
auto a = lower_bound(array, array+n, x); auto b = upper_bound(array, array+n, x);
auto r = equal_range(array, array+n, x);

ITERATION
VECTOR(v) => forauto(x: v) cout << v << endl; OR INDEX BASED => for(int x = 0; x < v.size(); x++)	 cout << x << endl;
SET(s) => for (auto x: s) cout << x << endl;
MAP(mp) => for (auto x: mp) cout << x.first (key) << " " << x.second(VALUE) <<endl;

ITERATORS (ELEMS POINTING TO ELEMS IN DS LIKE begin() => points to first elem, end() => point to free location outside of ds after last elem)
set<int>::iterator it = s.begin() OR auto it = s.begin() (or s.end()--)
VALUE => *it
NEXT POS => it++ 
PREV POS => it-- 
FIND OPERATION RETURN ITERATOR => it = s.find(x) => if(it == s.end()) ITEM NOT FOUND else cout << *it << endl;
UNORDERED_SET DOES NOT SUPPORT lower_bound(x) and upper_bound(x) functions

MAP => Check key exists => mp.count(key)

STL DS => 
string
vector(supports back addition and deletion)
stack
queue
map(complete Binary Tree => O(logN) operations), unordered_map(hashing => O(1) operations)
set(complete Binary Tree => O(logN) operations), unordered_set(hashing => O(1) operations)
multiset(complete Binary Tree => O(logN) operations), unordered_multiset(hashing => O(1) operations) //ALLOWS MULTIPLE ENTRIES OF SAME ITEM
bitset(0/1 array)
// bitset<10> s(string("0010011010")) => supports indexing s[0], s[i] using 1 byte for each item
// .count() returns no. of ones, (|, &, xor (binary ops) can be used directly b/w 2 bitsets =>  a|b, a&b, a^b )
deque(supports front as well as back addition and deletion)
priority_queue (logN insert/remove => default added in decreasing order)
[for increasing order => priority_queue<int,vector<int>,greater<int>> q;]


POLICY BASED DS(G++) => 
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
// indexed set (set (indexed like array))
typedef tree<int,null_type,less<int>,rb_tree_tag,
tree_order_statistics_node_update> indexed_set

indexed_set s; (logN => find_by_order, order_of_key)
s.insert(2); s.insert(3); s.insert(7); s.insert(9);

//FIND_BY_ORDER
auto x = s.find_by_order(2); // iterator to element at 2nd index
cout << *x << "\n"; // 7

//ORDER_OF_KEY
cout << s.order_of_key(7) << "\n"; // 2 (index of element 7)
// if elem not present, then possible index like for 6 => returns 2


FOR GENERATING PERMUTATIONS OF VECTOR v,
do {
// process permutation
} while (next_permutation(v.begin(),v.end())); // C++ STANDARD LIBRARY FUNCTION
*/

### Prompt

Create a solution in cpp for the following problem:

You are playing the game "Arranging The Sheep". The goal of this game is to make the sheep line up. The level in the game is described by a string of length n, consisting of the characters '.' (empty space) and '*' (sheep). In one move, you can move any sheep one square to the left or one square to the right, if the corresponding square exists and is empty. The game ends as soon as the sheep are lined up, that is, there should be no empty cells between any sheep.

For example, if n=6 and the level is described by the string "**.*..", then the following game scenario is possible: 

  * the sheep at the 4 position moves to the right, the state of the level: "**..*."; 
  * the sheep at the 2 position moves to the right, the state of the level: "*.*.*."; 
  * the sheep at the 1 position moves to the right, the state of the level: ".**.*."; 
  * the sheep at the 3 position moves to the right, the state of the level: ".*.**."; 
  * the sheep at the 2 position moves to the right, the state of the level: "..***."; 
  * the sheep are lined up and the game ends. 



For a given level, determine the minimum number of moves you need to make to complete the level.

Input

The first line contains one integer t (1 ≤ t ≤ 10^4). Then t test cases follow.

The first line of each test case contains one integer n (1 ≤ n ≤ 10^6).

The second line of each test case contains a string of length n, consisting of the characters '.' (empty space) and '*' (sheep) — the description of the level.

It is guaranteed that the sum of n over all test cases does not exceed 10^6.

Output

For each test case output the minimum number of moves you need to make to complete the level.

Example

Input


5
6
**.*..
5
*****
3
.*.
3
...
10
*.*...*.**


Output


1
0
0
0
9

### Response

```cpp
#include <bits/stdc++.h>
#define fread freopen("input.txt", "r", stdin);
#define fwrite freopen("output.txt", "w", stdout);
#define endl "\n"
#define F first
#define vi vector<int>
#define vl vector<long>
#define vll vector<long long>
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define SQ(a) (a) * (a)
#define REP(i, a, b) for (int i = a; i <= b; i++)
typedef long long ll;

using namespace std;

int maxSumSubArr(int n, int arr[]); // Kadane => O(N)
void processSubset();
void genSubsets(int n);
void genSubsetsRecursive(int k, int n);

// Calculates Operator precedence with respect to other operators
int getPrec(char oprtr) {
    // Operators => *,/,%,+,-,&,^,| (all are left to right associative)
    switch (oprtr) {
        // Multiplication, Division, Modulus
        case '*':
        case '/':
        case '%':
            return 5; // max precedence

        // Addition, Subtraction
        case '+':
        case '-':
            return 4;

        // Bitwise AND
        case '&':
            return 3;

        // Bitwise XOR
        case '^':
            return 2;

        // Bitwise OR
        case '|':
            return 1; // base (min precedence)

        // Unrecognised operator
        default:
            return -1;
    }
}

// Checks if character represents a closing parenthesis
bool isOpeningBracket(char exp) {
    return (exp == '{' || exp == '(' || exp == '[') ? true : false;
}

// Checks if character represents a closing parenthesis
bool isClosingBracket(char exp) {
    return (exp == '}' || exp == ')' || exp == ']') ? true : false;
}

// Checks for Precedence of operator1 with respect to operator2
bool hasHigherPrec(char oper1, char oper2) {
    // If operator1 has higher precendence, return true else false
   return ((getPrec(oper1) > getPrec(oper2)) ? true: false);
}

// Checks if string is operatpr or not
bool isOperator(char token) {
    // Checks for +,-,*,/,%,^,&,| operators
    if (token == '+' || token == '-' || token == '*' || token == '/' 
        || token == '%' || token == '^' || token == '&' || token == '|')
        return true; // Operator
    
    // Not operator
    return false;
}

// Perform a mathematical operation (opr) between two integrer operands and return result
int performOperation(int op1, int op2, string opr) {
    // Addition
    if (opr == "+")
        return op1 + op2;
    // Subtraction
    else if (opr == "-")
        return op1 - op2;
    // Division (returns floor for float result)
    else if (opr == "/")
        return op1 / op2;
    // Multiplication
    else if (opr == "*")
        return op1 * op2;
    // Modulus
    else if (opr == "%")
        return op1 % op2;
    // Bitwise OR
    else if (opr == "|")
        return op1 | op2;
    // Bitwise XOR
    else if (opr == "^")
        return op1 ^ op2;
    // Bitwise AND
    else if (opr == "&")
        return op1 & op2;
    // Unrecognized operation
    return -1;
}


// Conversion of infix expression to postfix expression
string infixToPostfix(int exp_len, string infix_exp) {
    string postfix_exp = ""; // initialise an empty string for resultant postfix expression
    stack <char> stack; // initialise and empty stack 
    
    
    // While not reached end of expression read through each token
    int i = 0;
    char token = infix_exp[i]; 
	while (token) 
    {
        // Any expression in brackets is considered as whole and operator precedence not checked with elements outside bracket

        // If token is an operator
        if (isOperator(token)) {
            // While operators in stack with higher precedence that token and we do not encounter an opening brace in Stack
            while(!stack.empty() && hasHigherPrec(stack.top(), token) && !isOpeningBracket(stack.top())) {
                // Pop the operator from stack and append to resultant postfix expression
                postfix_exp += stack.top();
				stack.pop();
            }
            // Once no operator with higher precedence in stack than token => push token to stack
            stack.push(token);
        } 
        
        // If token is an opening parenthesis => push onto stack
        else if (isOpeningBracket(token)) {
            stack.push(token);
        } 
        
        // If token is closing parenthesis
        else if (isClosingBracket(token)) {
            // While not opening parenthesis of token encountered
            while(!stack.empty() && !isOpeningBracket(stack.top())) {
                // Pop the operators from stack and append to resultant postfix expression
                postfix_exp += stack.top();
				stack.pop();
            }
            // Pop the final opening parenthesis of token from stack (not included in postfix expression)
            stack.pop();
        }

        // If token is an operand
        else {
            // Append the token to resultant postfix expression
            postfix_exp += token;
        } 

        // If end of expression => update token as NULL
        i++;
		token = infix_exp[i]; 
    }

    // If operators left in stack after end of infix expression
    while(!stack.empty()) {
        // Pop the operators from stack and append to resultant postfix expression
        postfix_exp += stack.top();
		stack.pop();
    }

    // Return resultant postfix expression
    return postfix_exp;
}

void solve()
{
    ll len, ind = 0, cnt = 0, ans = 0;
    string s;
    cin >> len >> s;
    ll sheeps = 0;
    for(auto x: s)
        if(x == '*')
            sheeps++;
    sheeps = (sheeps+1)/2;
    REP(i, 0, len-1) {
        if(s[i] == '*') {
            cnt++;
            if(cnt == sheeps) {
                ind = i;
                break;
            }
        }
    }
    cnt = 0;
    for(int j = ind-1; j >= 0; j--) {
        if(s[j] == '.')
            cnt++;
        else
            ans += cnt;
    }
    cnt = 0;
    for(int j = ind+1; j < len; j++) {
        if(s[j] == '.')
            cnt++;
        else
            ans += cnt;    
    }
    cout << ans << endl;
}


int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int tc;
	cin >> tc;
	while (tc--)
	{
	solve();
	}
}

/*
bool ready[int(1e5)];
int value[int(1e5)];
int minCoinForSumRecursive(int x, vi coins)
{
	if (x < 0)
		return INT_MAX;
	if (x == 0)
		return 0;
	if (ready[x])
		return value[x];

	int best = INT_MAX;
	for (auto c : coins)
		best = min(best, minCoinForSum(x - c) + 1);

	value[x] = best;
	ready[x] = true;

	return best;
}*/

/*
void nQueens(int y)
{
	if (y == n)
	{
		count++;
		return;
	}
	for (int x = 0; x < n; x++)
	{
		if (column[x] || diag1[x + y] || diag2[x - y + n - 1])
			continue;
		column[x] = diag1[x + y] = diag2[x - y + n - 1] = 1;
		nQueens(y + 1);
		column[x] = diag1[x + y] = diag2[x - y + n - 1] = 0;
	}
}
*/
// Only change this and call genSubsets(n)
void processSubset(vi v)
{
	for (auto x : v)
		cout << x << " ";
	cout << endl;
}

// Subsets of numbers => 0...n (FOR 2 =>  {}, {1}, {2}, {1,2})
void genSubsets(int n)
{
	for (int b = 0; b < (1 << n); b++)
	{
		vi subset;
		REP(i, 0, n - 1)
		{
			if (b & (1 << i))
				subset.push_back(i);
		}
		// HERE PROCESS SUBSET (USING SUBSET VECTOR)
		processSubset(subset);
	}
}

// Subsets of numbers => 0...n (FOR 2 =>  {}, {1}, {2}, {1,2})
/* vi subset;
void genSubsetsRecursive(int k, int n) // CALL => genSubsetsRecurive(0, n)
{
	if (k == n)
	{
		// HERE PROCESS SUBSET (USING SUBSET VECTOR)
	}
	else
	{
		genSubsetsRecursive(k + 1, n);
		subset.push_back(k);
		genSubsetsRecursive(k + 1, n);
		subset.pop_back();
	}
}
*/

int maxSumSubArr(int n, int arr[])
{
	// 0 size subarray allowed => max_sum >= 0
	int max_sum = 0, cur_sum = 0;
	REP(i, 0, n - 1)
	{
		cur_sum = max(arr[i], cur_sum + arr[i]);
		max_sum = max(max_sum, cur_sum);
	}

	return max_sum;
}

/*

COMMON METHODS
push pair<int, int> in vector => v.push_back({x,y}) OR v.push_back(make_pair(x,y))
push tuple<int, int, int> in vector => v.push_back({x,y,z}) OR v.push_back(make_tuple(x,y,z))
sort arr = sort(arr, arr+len) // can take third argument as comparison operator to be used for sorting (bool)
sort vector = sort(v.begin(), v.end()) (FOR PAIRS/TUPLE ON BASIS OF FIRST ITEM, IF SAME THEN SECOND AND SO ON)
sort vector rev = sort(v.rbegin(), v.rend()) 
reverse(v.begin(), v.end()) OR reverse(a, a+n) // reverse
random_shuffle(v.begin(), v.end()) OR random_shuffle(a, a+n) // shuffle

BINARY SEARCH (ONLY FOR SORTED ARRAYS)
lower_bound(arr, arr+len, x) => pointer to first item with value >=x
upper_bound(arr, arr+len, x) => pointer to first item with value >x
equal_range(arr, arr+len, x) => Pair of lower_bound(.first) and upper_bound pointer(.second)

auto k = lower_bound(arr, arr+n, x)-arr; // bin search equiv
if (k < n && array[k] == x) // x found at index k else x not present

Frequency of x in arr (difference b/w upper_bound and lower_bound => b-a OR r.second-r.first)
auto a = lower_bound(array, array+n, x); auto b = upper_bound(array, array+n, x);
auto r = equal_range(array, array+n, x);

ITERATION
VECTOR(v) => forauto(x: v) cout << v << endl; OR INDEX BASED => for(int x = 0; x < v.size(); x++)	 cout << x << endl;
SET(s) => for (auto x: s) cout << x << endl;
MAP(mp) => for (auto x: mp) cout << x.first (key) << " " << x.second(VALUE) <<endl;

ITERATORS (ELEMS POINTING TO ELEMS IN DS LIKE begin() => points to first elem, end() => point to free location outside of ds after last elem)
set<int>::iterator it = s.begin() OR auto it = s.begin() (or s.end()--)
VALUE => *it
NEXT POS => it++ 
PREV POS => it-- 
FIND OPERATION RETURN ITERATOR => it = s.find(x) => if(it == s.end()) ITEM NOT FOUND else cout << *it << endl;
UNORDERED_SET DOES NOT SUPPORT lower_bound(x) and upper_bound(x) functions

MAP => Check key exists => mp.count(key)

STL DS => 
string
vector(supports back addition and deletion)
stack
queue
map(complete Binary Tree => O(logN) operations), unordered_map(hashing => O(1) operations)
set(complete Binary Tree => O(logN) operations), unordered_set(hashing => O(1) operations)
multiset(complete Binary Tree => O(logN) operations), unordered_multiset(hashing => O(1) operations) //ALLOWS MULTIPLE ENTRIES OF SAME ITEM
bitset(0/1 array)
// bitset<10> s(string("0010011010")) => supports indexing s[0], s[i] using 1 byte for each item
// .count() returns no. of ones, (|, &, xor (binary ops) can be used directly b/w 2 bitsets =>  a|b, a&b, a^b )
deque(supports front as well as back addition and deletion)
priority_queue (logN insert/remove => default added in decreasing order)
[for increasing order => priority_queue<int,vector<int>,greater<int>> q;]


POLICY BASED DS(G++) => 
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
// indexed set (set (indexed like array))
typedef tree<int,null_type,less<int>,rb_tree_tag,
tree_order_statistics_node_update> indexed_set

indexed_set s; (logN => find_by_order, order_of_key)
s.insert(2); s.insert(3); s.insert(7); s.insert(9);

//FIND_BY_ORDER
auto x = s.find_by_order(2); // iterator to element at 2nd index
cout << *x << "\n"; // 7

//ORDER_OF_KEY
cout << s.order_of_key(7) << "\n"; // 2 (index of element 7)
// if elem not present, then possible index like for 6 => returns 2


FOR GENERATING PERMUTATIONS OF VECTOR v,
do {
// process permutation
} while (next_permutation(v.begin(),v.end())); // C++ STANDARD LIBRARY FUNCTION
*/

```