static void resort(char[] s) {
        int n = s.length;
        int[] f = new int[n];
        int count = 0;
        for (int i=n-1; i>=0; i--) {
            if (s[i] != '#') {
                f[i] = count;
            } else {
                count ++;
            }
        }

        for (int i=n-1; i>=0; i--) {
            if (s[i] != '#') {
                s[i+f[i]] = s[i];
            }
        }
        for (int i=0; i<count; i++) {
            s[i] = '#';
        }

    }