【atcoder beginner 308E - MEX】

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.ArrayList;
import java.util.List;

public class Main {

    public static Integer[] dp(int[] arr, String s,int t,char ch) {
        List<Integer> ans = new ArrayList<>();
        if (arr[0] == t && s.charAt(0) == ch) {
            ans.add(1);
        } else {
            ans.add(0);
        }
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] == t && s.charAt(i) == ch) {
                ans.add(ans.get(i - 1) + 1);
            } else {
                ans.add(ans.get(i - 1));
            }
        }
        return ans.toArray(new Integer[ans.size()]);
    }

    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int n = (int) in.nval;
        int[] arr = new int[n];
        for (int i = 0; i < arr.length; i++) {
            in.nextToken();
            arr[i] = (int) in.nval;
        }
        in.nextToken();
        String s = in.sval;
        Integer[] mlist = build(s, 'M');
        Integer[] elist = build(s, 'E');
        Integer[] xlist = build(s, 'X');

        Integer[] hm0 = dp(arr, s,0,'M');
        Integer[] hm1 = dp(arr, s,1,'M');
        Integer[] hm2 = dp(arr,s, 2,'M');

        Integer[] hx0 = dp(arr, s,0,'X');
        Integer[] hx1 = dp(arr, s,1,'X');
        Integer[] hx2 = dp(arr,s, 2,'X');


        long ans = 0;
        for (int i = 0; i < elist.length; i++) {
            int j = upperlound(mlist, elist[i]);
            int p = upperlound(xlist, elist[i]);

            if (j == 0) {
                continue;
            }
            if (p == xlist.length) {
                continue;
            }
            j = j - 1;

            int t = mlist[j];

            int x0 = hm0[t];
            int x1 = hm1[t];
            int x2 = hm2[t];

            int k = xlist[p];

            int y0 = k > 0 ? hx0[n - 1] - hx0[k - 1] : hx0[n - 1];
            int y1 = k > 0 ? hx1[n - 1] - hx1[k - 1] : hx1[n - 1];
            int y2 = k > 0 ? hx2[n - 1] - hx2[k - 1] : hx2[n - 1];

            int z = arr[elist[i]];

            if (z == 2) {
                ans += 1l*x0*(y0 + y2 + 3 * y1);
                ans += 3l*x1*y0;
                ans += 1l* x2*y0;
            }
            else if( z == 1){
                ans += 1l*x0*(2*y0+2*y1+3*y2);
                ans += 2l*x1*y0;
                ans += 3l*x2*y0;
            }
            else{
                ans += 1l*x0*(y0+2*y1+y2);
                ans += 1l*x1*(2*y0+2*y1+3*y2);
                ans += 1l*x2*(y0+3*y1+y2);
            }

        }

        System.out.println(ans);
    }


    /**
     * @param arr
     * @param value
     * @return 》 value的第一个坐标位置，如果不存在，那么就是arr.length;
     */
    public static int upperlound(Integer[] arr, int value) {
        int low = 0;
        int high = arr.length;
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (arr[mid] <= value) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return low;
    }

    public static Integer[] build(String str, char ch) {
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == ch) {
                list.add(i);
            }
        }
        return list.toArray(new Integer[list.size()]);
    }


}