#include <iostream>
#include <unordered_set>
#include <vector>

using namespace std;

struct DPState {
  int pos;
  int last_jump;

  std::size_t operator()(DPState const& s) const noexcept {
    std::size_t h1 = std::hash<int>{}(s.pos);
    std::size_t h2 = std::hash<int>{}(s.last_jump);
    return h1 ^ (h2 << 1);
  }

  bool operator()(const DPState& lhs, const DPState& rhs) const {
    return lhs.pos == rhs.pos && lhs.last_jump == rhs.last_jump;
  }
};

using DPStateSet = unordered_set<DPState, DPState, DPState>;

bool can_cross(const unordered_set<int>& stones, int pos, int last_jump,
               int target, DPStateSet* already_explored) {
  if (pos == target) {
    return true;
  }
  DPState dp_state({/*pos=*/pos, /*last_jump=*/last_jump});
  if (already_explored->count(dp_state)) {
    return false;
  }

  unordered_set<int> possible_jumps = {last_jump, last_jump + 1};
  if (last_jump > 1) {
    possible_jumps.insert(last_jump - 1);
  }
  for (int jump : possible_jumps) {
    int new_pos = pos + jump;
    if (stones.count(new_pos) > 0) {
      if (can_cross(stones, new_pos, jump, target, already_explored)) {
        return true;
      }
    }
  }
  already_explored->insert(dp_state);
  return false;
}

class Solution {
public:
  bool canCross(const vector<int>& stones_vec) {
    unordered_set<int> stones(stones_vec.begin(), stones_vec.end());
    if (stones.count(1) == 0) {
      return false;
    }
    DPStateSet already_explored;
    return can_cross(stones, /*pos=*/1, /*last_jump=*/1, stones_vec.back(),
                     &already_explored);
  }
};

int main() {
  // [0,1,3,5,6,8,12,17]
  // [0,1,3,4,5,7,9,10,12]
  // [0,1,2,3,4,8,9,11]
  // [0,1]
  // [0,2]
  cout << Solution().canCross({0, 1, 3, 5, 6, 8, 12, 17}) << endl;
  return 0;
}