Takahashi found an integer sequence (A_1,A_2,...,A_N) with N terms. Since it was too heavy to carry, he decided to compress it into a single integer.

The compression takes place in N-1 steps, each of which shorten the length of the sequence by 1. Let S be a string describing the steps, and the sequence on which the i-th step is performed be (a_1,a_2,...,a_K), then the i-th step will be as follows:

* When the i-th character in S is `M`, let b_i = max(a_i,a_{i+1}) (1 ≦ i ≦ K-1), and replace the current sequence by (b_1,b_2,...,b_{K-1}).
* When the i-th character in S is `m`, let b_i = min(a_i,a_{i+1}) (1 ≦ i ≦ K-1), and replace the current sequence by (b_1,b_2,...,b_{K-1}).



Takahashi decided the steps S, but he is too tired to carry out the compression. On behalf of him, find the single integer obtained from the compression.

Constraints

* 2 ≦ N ≦ 10^5
* 1 ≦ A_i ≦ N
* S consists of N-1 characters.
* Each character in S is either `M` or `m`.

Input

The input is given from Standard Input in the following format:


N
A_1 A_2 … A_N
S


Output

Print the single integer obtained from the compression.

Examples

Input

4
1 2 3 4
MmM


Output

3


Input

5
3 4 2 2 1
MMmm


Output

2


Input

10
1 8 7 6 8 5 2 2 6 1
MmmmmMMMm


Output

5


Input

20
12 7 16 8 7 19 8 19 20 11 7 13 20 3 4 11 19 11 15 5
mMMmmmMMMMMMmMmmmMM


Output

11
#include <bits/stdc++.h>
using namespace std;

using ll=long long;
#define int ll

#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define per(i,b) gnr(i,0,b)
#define pb push_back
#define eb emplace_back
#define a first
#define b second
#define bg begin()
#define ed end()
#define all(x) x.bg,x.ed
#ifdef LOCAL
#define dmp(x) cerr<<__LINE__<<" "<<#x<<" "<<x<<endl
#else
#define dmp(x) void(0)
#endif

template<class t,class u> void chmax(t&a,u b){if(a<b)a=b;}
template<class t,class u> void chmin(t&a,u b){if(b<a)a=b;}

template<class t> using vc=vector<t>;
template<class t> using vvc=vc<vc<t>>;

using pi=pair<int,int>;
using vi=vc<int>;

template<class t,class u>
ostream& operator<<(ostream& os,const pair<t,u>& p){
	return os<<"{"<<p.a<<","<<p.b<<"}";
}

template<class t> ostream& operator<<(ostream& os,const vc<t>& v){
	os<<"{";
	for(auto e:v)os<<e<<",";
	return os<<"}";
}

#define mp make_pair
#define mt make_tuple
#define one(x) memset(x,-1,sizeof(x))
#define zero(x) memset(x,0,sizeof(x))
#ifdef LOCAL
void dmpr(ostream&os){os<<endl;}
template<class T,class... Args>
void dmpr(ostream&os,const T&t,const Args&... args){
	os<<t<<" ";
	dmpr(os,args...);
}
#define dmp2(...) dmpr(cerr,"Line:",__LINE__,##__VA_ARGS__)
#else
#define dmp2(...) void(0)
#endif

using uint=unsigned;
using ull=unsigned long long;

template<class t,size_t n>
ostream& operator<<(ostream&os,const array<t,n>&a){
	return os<<vc<t>(all(a));
}

template<int i,class T>
void print_tuple(ostream&,const T&){
}

template<int i,class T,class H,class ...Args>
void print_tuple(ostream&os,const T&t){
	if(i)os<<",";
	os<<get<i>(t);
	print_tuple<i+1,T,Args...>(os,t);
}

template<class ...Args>
ostream& operator<<(ostream&os,const tuple<Args...>&t){
	os<<"{";
	print_tuple<0,tuple<Args...>,Args...>(os,t);
	return os<<"}";
}

void print(ll x,int suc=1){
	cout<<x;
	if(suc==1)
		cout<<"\n";
	if(suc==2)
		cout<<" ";
}

ll read(){
	ll i;
	cin>>i;
	return i;
}

vi readvi(int n,int off=0){
	vi v(n);
	rep(i,n)v[i]=read()+off;
	return v;
}

template<class T>
void print(const vector<T>&v,int suc=1){
	rep(i,v.size())
		print(v[i],i==int(v.size())-1?suc:2);
}

string readString(){
	string s;
	cin>>s;
	return s;
}

template<class T>
T sq(const T& t){
	return t*t;
}

//#define CAPITAL
void yes(bool ex=true){
	#ifdef CAPITAL
	cout<<"YES"<<endl;
	#else
	cout<<"Yes"<<endl;
	#endif
	if(ex)exit(0);
}
void no(bool ex=true){
	#ifdef CAPITAL
	cout<<"NO"<<endl;
	#else
	cout<<"No"<<endl;
	#endif
	if(ex)exit(0);
}
void possible(bool ex=true){
	#ifdef CAPITAL
	cout<<"POSSIBLE"<<endl;
	#else
	cout<<"Possible"<<endl;
	#endif
	if(ex)exit(0);
}
void impossible(bool ex=true){
	#ifdef CAPITAL
	cout<<"IMPOSSIBLE"<<endl;
	#else
	cout<<"Impossible"<<endl;
	#endif
	if(ex)exit(0);
}

constexpr ll ten(int n){
	return n==0?1:ten(n-1)*10;
}

const ll infLL=LLONG_MAX/3;

#ifdef int
const int inf=infLL;
#else
const int inf=INT_MAX/2-100;
#endif

int topbit(signed t){
	return t==0?-1:31-__builtin_clz(t);
}
int topbit(ll t){
	return t==0?-1:63-__builtin_clzll(t);
}
int botbit(signed a){
	return a==0?32:__builtin_ctz(a);
}
int botbit(ll a){
	return a==0?64:__builtin_ctzll(a);
}
int popcount(signed t){
	return __builtin_popcount(t);
}
int popcount(ll t){
	return __builtin_popcountll(t);
}
bool ispow2(int i){
	return i&&(i&-i)==i;
}
int mask(int i){
	return (int(1)<<i)-1;
}

bool inc(int a,int b,int c){
	return a<=b&&b<=c;
}

template<class t> void mkuni(vc<t>&v){
	sort(all(v));
	v.erase(unique(all(v)),v.ed);
}

ll rand_int(ll l, ll r) { //[l, r]
	#ifdef LOCAL
	static mt19937_64 gen;
	#else
    static random_device rd;
    static mt19937_64 gen(rd());
    #endif
    return uniform_int_distribution<ll>(l, r)(gen);
}

template<class t>
int lwb(const vc<t>&v,const t&a){
	return lower_bound(all(v),a)-v.bg;
}

signed main(){
	cin.tie(0);
	ios::sync_with_stdio(0);
	cout<<fixed<<setprecision(20);
	
	int n;cin>>n;
	vi a=readvi(n,-1);
	string s;cin>>s;
	
	int lw=0,up=n;
	while(up-lw>1){
		const int mid=(lw+up)/2;
		
		vi val(n);
		rep(i,n)val[i]=a[i]>=mid;
		vi cnt(n);
		vi u(n);
		vi nx(n+1,-1),pr(n+1,-1);
		int root=n;
		nx[root]=root;
		pr[root]=root;
		auto link=[&](int i,int j){
			nx[i]=j;
			pr[j]=i;
		};
		auto insert=[&](int i,int j){
			link(j,nx[i]);
			link(i,j);
		};
		auto erase=[&](int i){
			link(pr[i],nx[i]);
		};
		{
			int pre=-1;
			rep(i,n){
				if(val[i]!=pre){
					insert(pr[root],i);
					u[i]=1;
					pre=val[i];
				}
				cnt[pr[root]]++;
			}
		}
		int off[2]{};
		priority_queue<pi,vc<pi>,greater<pi>> pq[2];
		rep(i,n)if(u[i])
			pq[val[i]].emplace(cnt[i],i);
		
		auto modify_edge=[&](int i,int k){
			if(val[i]==k){
				cnt[i]--;
				pq[val[i]].emplace(cnt[i],i);
			}
		};
		
		int rem=accumulate(all(u),0);
		auto del=[&](int i){
			u[i]=0;
			rem--;
			erase(i);
		};
		
		for(auto op:s){
			int k=op=='M';
			if(rem==1)break;
			
			modify_edge(nx[root],k);
			modify_edge(pr[root],k);
			
			off[k]++;
			off[k^1]--;
			
			while(pq[k^1].size()){
				int c,i;tie(c,i)=pq[k^1].top();
				if(cnt[i]!=c||!u[i]){
					pq[k^1].pop();
					continue;
				}
				c+=off[k^1];
				assert(c>=0);
				if(c==0){
					int p=pr[i],q=nx[i];
					if(p!=root&&q!=root){
						cnt[p]+=cnt[q]+off[val[q]];
						pq[val[p]].emplace(cnt[p],p);
						del(q);
					}
					del(i);
					pq[k^1].pop();
				}else
					break;
			}
		}
		if(val[nx[root]])
			lw=mid;
		else
			up=mid;
	}
	cout<<lw+1<<endl;
}
