import java.util.*;
import java.util.zip.*;
import java.util.List;
import java.util.regex.*;
import java.util.concurrent.*;
import java.util.concurrent.atomic.*;
import java.util.concurrent.locks.*;
import javax.swing.*;
import javax.swing.event.*;
import javax.swing.text.*;
import javax.swing.table.*;
import java.io.*;
import java.net.*;
import java.lang.reflect.*;
import java.lang.ref.*;
import java.lang.management.*;
import java.security.*;
import java.security.spec.*;
import java.awt.*;
import java.awt.event.*;
import java.awt.image.*;
import javax.imageio.*;
import java.math.*;
class main {

static int intArrayBinarySearchWithGeneralizedComparator(int[] a, IF1_IntToInt comparator) {
  return intArrayBinarySearchWithGeneralizedComparator(a, 0, a.length, comparator);
}

static int intArrayBinarySearchWithGeneralizedComparator(int[] a, int fromIndex, int toIndex, IF1_IntToInt comparator) {
  int low = fromIndex;
  int high = toIndex - 1;

  while (low <= high) {
    int mid = (low + high) >>> 1;
    int midVal = a[mid];

    int cmp = comparator.get(midVal);
    if (cmp < 0)
        low = mid + 1;
    else if (cmp > 0)
        high = mid - 1;
    else
        return mid; // key found
  }
  return -(low + 1);  // key not found.
}
static interface IF1_IntToInt {
  int get(int i);
}
}