Luba needs your help again! Luba has n TV sets. She knows that i-th TV set will be working from moment of time li till moment ri, inclusive.

Luba wants to switch off one of TV sets in order to free the socket. Let's call some TV set redundant if after switching it off the number of integer moments of time when at least one of TV sets is working won't decrease. Luba will be very upset if she has to switch off a non-redundant TV set.

Help Luba by telling her the index of some redundant TV set. If there is no any, print -1.

Input

The first line contains one integer number n (1 ≤ n ≤ 2·105) — the number of TV sets.

Then n lines follow, each of them containing two integer numbers li, ri (0 ≤ li ≤ ri ≤ 109) denoting the working time of i-th TV set.

Output

If there is no any redundant TV set, print -1. Otherwise print the index of any redundant TV set (TV sets are indexed from 1 to n).

If there are multiple answers, print any of them.

Examples

Input

3
1 3
4 6
1 7


Output

1


Input

2
0 10
0 10


Output

1


Input

3
1 2
3 4
6 8


Output

-1


Input

3
1 2
2 3
3 4


Output

2

Note

Consider the first sample. Initially all integer moments of time such that at least one TV set is working are from the segment [1;7]. It's easy to see that this segment won't change if we switch off the first TV set (or the second one).

Note that in the fourth sample you can switch off the second TV set, since even without it all integer moments such that any of the TV sets is working denote the segment [1;4].
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Iterator;
import java.io.BufferedWriter;
import java.util.Collection;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Jialin Ouyang (Jialin.Ouyang@gmail.com)
 */
public class Main {
  public static void main(String[] args) {
    InputStream inputStream = System.in;
    OutputStream outputStream = System.out;
    QuickScanner in = new QuickScanner(inputStream);
    QuickWriter out = new QuickWriter(outputStream);
    TaskE solver = new TaskE();
    solver.solve(1, in, out);
    out.close();
  }

  static class TaskE {
    int n;
    int[] lower;
    int[] upper;
    IntPriorityQueue lowerPQ;
    IntPriorityQueue upperPQ;
    boolean[] isIn;
    IntArrayDeque inQ;
    boolean[] valid;

    public void solve(int testNumber, QuickScanner in, QuickWriter out) {
      n = in.nextInt();
      lower = new int[n];
      upper = new int[n];
      lowerPQ = new IntPriorityQueue(n, (x, y) -> lower[x] - lower[y]);
      upperPQ = new IntPriorityQueue(n, (x, y) -> upper[x] - upper[y]);
      for (int i = 0; i < n; ++i) {
        lower[i] = in.nextInt();
        upper[i] = in.nextInt() + 1;
        lowerPQ.add(i);
        upperPQ.add(i);
      }
      out.println(calc());
    }

    int calc() {
      isIn = new boolean[n];
      valid = new boolean[n];
      inQ = new IntArrayDeque(n);
      while (lowerPQ.isNotEmpty() || upperPQ.isNotEmpty()) {
        int ts = lowerPQ.isEmpty()
            ? upper[upperPQ.peek()]
            : Math.min(lower[lowerPQ.peek()], upper[upperPQ.peek()]);
        while (lowerPQ.isNotEmpty() && lower[lowerPQ.peek()] == ts) {
          int idx = lowerPQ.poll();
          isIn[idx] = true;
          inQ.addLast(idx);
        }
        while (upperPQ.isNotEmpty() && upper[upperPQ.peek()] == ts) {
          int idx = upperPQ.poll();
          isIn[idx] = false;
        }
        for (; inQ.isNotEmpty() && !isIn[inQ.peekFirst()]; inQ.pollFirst()) {
        }
        for (; inQ.isNotEmpty() && !isIn[inQ.peekLast()]; inQ.pollLast()) {
        }
        if (inQ.size() == 1) valid[inQ.peekLast()] = true;
      }
      for (int i = 0; i < n; ++i)
        if (!valid[i]) {
          return i + 1;
        }
      return -1;
    }

  }

  static class IntArrayDeque extends IntArrayQueue {
    public IntArrayDeque(int capacity) {
      super(capacity);
    }


    public void add(int value) {
      throw new UnsupportedOperationException();
    }

    public void addLast(int value) {
      super.add(value);
    }


    public int peek() {
      throw new UnsupportedOperationException();
    }

    public int peekFirst() {
      return super.peek();
    }

    public int peekLast() {
      if (open == close) throw new ArrayIndexOutOfBoundsException();
      return values[(close - 1) & (values.length - 1)];
    }


    public int poll() {
      throw new UnsupportedOperationException();
    }

    public int pollFirst() {
      return super.poll();
    }

    public int pollLast() {
      if (open == close) throw new ArrayIndexOutOfBoundsException();
      close = (close - 1) & (values.length - 1);
      return values[close];
    }

  }

  static interface IntCollection {
    int size();

    default boolean isEmpty() {
      return size() == 0;
    }

    default boolean isNotEmpty() {
      return size() > 0;
    }

  }

  static class IntPriorityQueue extends IntArrayList {
    private final IntComparator comparator;

    public IntPriorityQueue(int capacity) {
      this(capacity, (x, y) -> x - y);
    }

    public IntPriorityQueue(int capacity, IntComparator comparator) {
      super(capacity);
      this.comparator = comparator;
      clear();
    }


    public void add(int value) {
      super.add(value);
      int i = size - 1;
      while (i > 0) {
        int parent = (i - 1) >> 1;
        int parentValue = values[parent];
        if (comparator.compare(value, parentValue) >= 0) break;
        values[i] = parentValue;
        i = parent;
      }
      values[i] = value;
    }

    public int peek() {
      if (size == 0) throw new ArrayIndexOutOfBoundsException();
      return values[0];
    }

    public int poll() {
      if (size == 0) throw new ArrayIndexOutOfBoundsException();
      int res = values[0];
      int value = values[--size];
      int half = size >> 1;
      int i = 0;
      while (i < half) {
        int child = (i << 1) | 1;
        int childValue = values[child];
        int right = child + 1;
        if (right < size && comparator.compare(childValue, values[right]) > 0) {
          child = right;
          childValue = values[child];
        }
        if (comparator.compare(value, childValue) <= 0) break;
        values[i] = childValue;
        i = child;
      }
      values[i] = value;
      return res;
    }


    public String toString() {
      StringBuilder sb = new StringBuilder("[");
      for (int i = 0; i < size; ++i) {
        if (i > 0) sb.append(',').append(' ');
        sb.append(values[i]);
      }
      return sb.append(']').toString();
    }

  }

  static class QuickWriter {
    private final PrintWriter writer;

    public QuickWriter(OutputStream outputStream) {
      this.writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
    }

    public QuickWriter(Writer writer) {
      this.writer = new PrintWriter(writer);
    }

    public void print(Object... objects) {
      for (int i = 0; i < objects.length; ++i) {
        if (i > 0) {
          writer.print(' ');
        }
        writer.print(objects[i]);
      }
    }

    public void println(Object... objects) {
      print(objects);
      writer.print('\n');
    }

    public void close() {
      writer.close();
    }

  }

  static class IntUtils {
    public static boolean isPow2(int n) {
      return n > 0 && (n & (n - 1)) == 0;
    }

    public static int nextPow2(int n) {
      if (n < 1) return 1;
      return isPow2(n) ? n : Integer.highestOneBit(n) << 1;
    }

  }

  static interface IntComparator {
    int compare(int o1, int o2);

  }

  static class IntArrayQueue implements IntCollection, Displayable {
    private static int[] EMPTY = {};
    protected int[] values;
    protected int open;
    protected int close;

    public IntArrayQueue() {
      values = EMPTY;
      clear();
    }

    public IntArrayQueue(int capacity) {
      values = new int[Integer.highestOneBit(capacity) << 1];
      clear();
    }


    public void clear() {
      open = close = 0;
    }


    public int size() {
      return (close - open) & (values.length - 1);
    }


    public void add(int value) {
      ensureCapacity(size() + 1);
      values[close++] = value;
      close &= values.length - 1;
    }

    public int peek() {
      if (open == close) throw new ArrayIndexOutOfBoundsException();
      return values[open];
    }

    public int poll() {
      if (open == close) throw new ArrayIndexOutOfBoundsException();
      int res = values[open];
      open = (open + 1) & (values.length - 1);
      return res;
    }

    protected void ensureCapacity(int capacity) {
      if (capacity < values.length) return;
      int[] newValues = new int[Integer.highestOneBit(capacity) << 1];
      for (int i = 0, j = open; j != close; ++i, j = (j + 1) & (values.length - 1)) {
        newValues[i] = values[j];
      }
      close = size();
      open = 0;
      values = newValues;
    }

  }

  static class IntArrayList implements Displayable, IntCollection, Iterable<Integer> {
    private static final int[] EMPTY = {};
    public int[] values;
    public int size;

    public IntArrayList() {
      values = EMPTY;
      clear();
    }

    public IntArrayList(int capacity) {
      values = new int[IntUtils.nextPow2(capacity)];
      clear();
    }

    public IntArrayList(Collection<Integer> collection) {
      this(collection.size());
      addAll(collection);
    }


    public void clear() {
      size = 0;
    }


    public int size() {
      return size;
    }


    public void add(int value) {
      ensureCapacity(size + 1);
      addInternal(value);
    }


    public void addAll(Collection<Integer> values) {
      ensureCapacity(size + values.size());
      for (int value : values) {
        addInternal(value);
      }
    }

    public void ensureCapacity(int capacity) {
      if (capacity <= values.length) return;
      int[] newValues = new int[IntUtils.nextPow2(capacity)];
      for (int i = 0; i < size; ++i) {
        newValues[i] = values[i];
      }
      values = newValues;
    }


    public Iterator<Integer> iterator() {
      return new Iterator<Integer>() {
        private int i = 0;


        public boolean hasNext() {
          return i < size;
        }


        public Integer next() {
          return values[i++];
        }
      };
    }

    private void addInternal(int value) {
      values[size++] = value;
    }

  }

  static interface Displayable {
  }

  static class QuickScanner {
    private static final int BUFFER_SIZE = 1024;
    private InputStream stream;
    private byte[] buffer;
    private int currentPosition;
    private int numberOfChars;

    public QuickScanner(InputStream stream) {
      this.stream = stream;
      this.buffer = new byte[BUFFER_SIZE];
      this.currentPosition = 0;
      this.numberOfChars = 0;
    }

    public int nextInt() {
      int c = nextNonSpaceChar();
      boolean positive = true;
      if (c == '-') {
        positive = false;
        c = nextChar();
      }
      int res = 0;
      do {
        if (c < '0' || '9' < c) throw new RuntimeException();
        res = res * 10 + c - '0';
        c = nextChar();
      } while (!isSpaceChar(c));
      return positive ? res : -res;
    }

    public int nextNonSpaceChar() {
      int res = nextChar();
      for (; isSpaceChar(res) || res < 0; res = nextChar()) ;
      return res;
    }

    public int nextChar() {
      if (numberOfChars == -1) {
        throw new RuntimeException();
      }
      if (currentPosition >= numberOfChars) {
        currentPosition = 0;
        try {
          numberOfChars = stream.read(buffer);
        } catch (Exception e) {
          throw new RuntimeException(e);
        }
        if (numberOfChars <= 0) {
          return -1;
        }
      }
      return buffer[currentPosition++];
    }

    public boolean isSpaceChar(int c) {
      return c == ' ' || c == '\t' || isEndOfLineChar(c);
    }

    public boolean isEndOfLineChar(int c) {
      return c == '\n' || c == '\r' || c < 0;
    }

  }
}

