# HackerEarth Hard job problem solution

In this HackerEarth Hard job problem You are given a permutation of integers from 1 to N (very unusual :D). The only thing you should do is to process M queries. Each query has 2 parameters: number X from 1 to N and lowercase latin letter Y (either 'l' or 'r'). You do the following:

Calculate distances from the position of the number X to the left end and to the right end of the permutation. Let's call minimum of them accessibleness.
Erase number X from it's current position. If parameter Y is 'l' then insert X the very beginning of the permutation. Otherwise insert X after the last element of the permutation.
Please find sum of accessibleness over all queries.

## HackerEarth Hard job problem solution.

`#include <cstdio>#include <algorithm>#include <vector>#include <iostream>#include <set>#include <map>#include <iomanip>#include <string>#include <string.h>#include <cstdlib>#include <bitset>#include <cmath>#define X first#define Y second#define mp make_pair#define pb push_backtypedef long long ll;using namespace std;const int MAXN = 300100, MX = MAXN * 3;int r[MX];void modify(int x, int y) {    for (; x < MX; x = (x|(x + 1))) {        r[x] += y;    }}int sum(int x) {    int res = 0;    for (; x >= 0; x = ((x&(x + 1) ) -1) ) {        res += r[x];    }    return res;}int lft = MAXN, rght, n, m;int wh[MAXN];int main() {    scanf("%d%d", &n, &m);    rght = lft + n - 1;    for (int i = 0; i < n; i++) {        modify(lft + i, 1);        int x;        scanf("%d", &x);        wh[x] = lft + i;    }    long long ans = 0;    for (int i = 0; i < m; i++) {        int x;        char go[5];        scanf("%d%s", &x, go);        int A = sum(wh[x]);        int B = sum(rght);        ans += min(A - 1, B - A);        modify(wh[x], -1);        if (go[0] == 'l') {            lft--;            wh[x] = lft;            modify(lft, 1);        }        else {            rght++;            wh[x] = rght;            modify(rght, 1);        }    }    cout<<ans<<endl;    return 0;}`

### Second solution

`#include<bits/stdc++.h>using namespace std;int t[1<<21];int n,m;int q,ps[1<<20],ptrl,ptrr;string st;long long ans;int sum(int r){    int res=0;    for (;r>=0;r=(r&(r+1))-1)        res+=t[r];    return res;}void add(int i, int val){       for (;i<=m*2+n+5;i=(i|(i+1)))        t[i]+=val;}int sum(int l,int r){    return sum(r)-sum(l-1);}int main(){ios_base::sync_with_stdio(0);cin>>n>>m;for (int i=1;i<=n;i++){    cin>>q;    ps[q]=i+m;}ptrl=m;ptrr=m+n+1;for (int i=1;i<=n;i++){    add(i+m,1);}int mm=m;for (;mm;--mm){    cin>>q;    cin>>st;    int res=min(sum(0,ps[q]),sum(ps[q],m*2+n+2));    ans+=res;        if (st=="l") // end        add(ptrl,1),        add(ps[q],-1),        ps[q]=ptrl,        --ptrl;    else        add(ps[q],-1),// l        add(ptrr,1),        ps[q]=ptrr,        ++ptrr;}cout<<ans<<endl;return 0;}`