1
class Solution {
2
  int firstPlayer, secondPlayer, n;
3

4
  boolean enumerate(ArrayList<Integer> ret, int mask, int start, int end) {
5
    if (start >= end) {
6
      ret.add(mask);
7
      return false;
8
    } else {
9
      while ((start < end) && ((mask & (1 << start)) != 0)) start++;
10
      while ((start < end) && ((mask & (1 << end)) != 0)) end--;
11
      if (start >= end) return enumerate(ret, mask, start + 1, end - 1);
12
      else if (start == firstPlayer && end == secondPlayer) return true;
13
      else if (start == firstPlayer || start == secondPlayer)
14
        return enumerate(ret, mask | 1 << end, start + 1, end - 1);
15
      else if (end == firstPlayer || end == secondPlayer)
16
        return enumerate(ret, mask | 1 << start, start + 1, end - 1);
17
      else
18
        return enumerate(ret, mask | 1 << start, start + 1, end - 1)
19
            || enumerate(ret, mask | 1 << end, start + 1, end - 1);
20
    }
21
  }
22

23
  int minDFS(int mask) {
24
    int start = 0, end = n - 1;
25
    ArrayList<Integer> arr = new ArrayList<Integer>();
26
    if (enumerate(arr, mask, start, end)) return 1;
27
    else {
28
      int q = Integer.MAX_VALUE;
29
      for (int x : arr) q = Math.min(q, 1 + minDFS(x));
30
      return q;
31
    }
32
  }
33

34
  int maxDFS(int mask) {
35
    int start = 0, end = n - 1;
36
    ArrayList<Integer> arr = new ArrayList<Integer>();
37
    if (enumerate(arr, mask, start, end)) return 1;
38
    else {
39
      int q = Integer.MIN_VALUE;
40
      for (int x : arr) q = Math.max(q, 1 + maxDFS(x));
41
      return q;
42
    }
43
  }
44

45
  public int[] earliestAndLatest(int n, int firstPlayer, int secondPlayer) {
46
    this.n = n;
47
    this.firstPlayer = firstPlayer - 1;
48
    this.secondPlayer = secondPlayer - 1;
49
    return new int[] {minDFS(0), maxDFS(0)};
50
  }
51
}