public class D {
    
    
    /** Exchage the entries at i and j in the array b. */
    private static void swap(int[] b, int i, int j) {
        int t= b[i];
        b[i]= b[j];
        b[j]= t;
    }
    
    
    /** Exchage the entries at i and j in the array b. */
    private static void swap(char[] b, int i, int j) {
        char t= b[i];
        b[i]= b[j];
        b[j]= t;
    }
    
    
    /** = the minimum of all the values in b.
      * Precondition: b.length > 0 */
    public static int min(int[] b) {
        int n= b.length;
  
        // pre: nothing known about contents of b
        //        0                       n
        // or: b:[           ?           ]
  
        int k= 1, x= b[0];
  
        // inv: x is the min of b[0..k-1]
        //        0            k          n
        // or: b:[  x is min  |     ?    ]
        while (k != n) {
            x= Math.min(x, b[k]);
            k= k+1;
        }
        // R: x is the min of b[0..n-1]
        //        0            k          n
        // or: b:[       x is min        ]

        return x;
    }
    
    
    /** Partition the array b into negative and nonnegative values.
      * Permute the values in b and return an integer k so that 
      * b[0..k-1] are negative and b[k..] are nonnegative. */
    public static int posNeg(int[] b) {
        int n= b.length;
        
        // pre: nothing known about contents of b
        //        0                       n
        // or: b:[           ?           ]
        
        int i= 0, k= 0;
        
        // inv: b[0..k-1] < 0; b[k..i-1] >= 0
        //        0       k        i      n
        // or: b:[  < 0  |  >= 0  |  ?   ]
        while (i != n) {
            if (b[i] < 0) {
                swap(b, k, i);
                k= k+1;
            }
            i= i+1;
        }
        
        // R: b[0..k-1] < 0; b[k..] >= 0
        //        0           k           n
        // or: b:[    < 0    |   >= 0    ]
        
        return k;
    }
    

    /** Permute the entries of b so that all "R"s come before all
      * "W"s which come before all "B"s. 
      * Precondition: b contains only the characters R, W, and B. */
    public static void flag1(char[] b) {
        int n= b.length;
        
        // pre: b contains Rs, Ws, Bs; nothing known about order
        //        0                       n
        // or: b:[           ?           ]
        
        int i= 0, j= 0, k= 0;
        
        // inv: b[0..i-1] are R; b[i..j-1] are W; b[j..k-1] are B
        //        0     i     j     k     n
        // or: b:[  R  |  W  |  B  |  ?  ]
        while (k < n) {
            if (b[k] == 'R') {
                swap(b, i, k);
                swap(b, j, k);
                i= i+1;
                j= j+1;
                k= k+1;
            } else if (b[k] == 'W') {
                swap(b, j, k);
                j= j+1;
                k= k+1;
            } else {  // b[k] == 'B'
                k= k+1;
            }
        }
        // R: b has Rs first, followed by Ws, followed by Bs.
        //        0                       n
        // or: b:[   R   |   W   |   B   ]
    }
    
    
    /** Permute the entries of b so that all "R"s come before all
      * "W"s which come before all "B"s. 
      * Precondition: b contains only the characters R, W, and B. */
    public static void flag2(char[] b) {
        int n= b.length;
        
        // pre: b contains Rs, Ws, Bs; nothing known about order
        //        0                       n
        // or: b:[           ?           ]
        
        int i= 0, j= 0, k= n;
        
        // inv: b[0..i-1] are R; b[i..j-1] are W; b[j..k-1] are B
        //        0     i     j     k     n
        // or: b:[  R  |  W  |  ?  |  B  ]
        while (j != k) {
            if (b[j] == 'R') {
                swap(b, i, j);
                i= i+1;
                j= j+1;
            } else if (b[j] == 'W') {
                j= j+1;
            } else {  // b[j] == 'B'
                swap(b, j, k-1);
                k= k-1;
            }
        }
        // R: b has Rs first, followed by Ws, followed by Bs.
        //        0                       n
        // or: b:[   R   |   W   |   B   ]
    }
    
    
    /** = the final position of x, after the subarray b[h..k] is partitioned 
      * by putting elements < x before x and elements > x after x, where x is
      * the value initially in b[h].
      * Precondition: 0 <= h <= k < b.length */
    public static int partition(int[] b, int h, int k) {
        
        // pre: b[h] == x
        //        h                         k
        // or: b:[x|            ?            ]
        int j= h, i= k+1;
        
        // inv: b[j] == x; b[h..j-1] <= x; b[i..k] >= x
        //        h        j         i      k
        // or: b:[   <=   |x|   ?   |   >=   ]
        while (i - j > 1) {
            if (b[j+1] < b[j]) {
                swap(b, j, j+1);
                j= j+1;
            } else {
                swap(b, j+1, i-1);
                i= i-1;
            }
        }
        // R: b[j] == x; b[h..j-1] <= x; b[j+1..k] >= x
        //        h            j            k
        // or: b:[     <=     |x|     >=     ]
        
        return j;
    }
        
    
}