sclass MountainsAndValleys {
  settable double[] values;
  gettable new IntBuffer highs;
  gettable new IntBuffer lows;
  
  *() {}
  *(double[] *values) {}

  run {
    int n = l(values);
    if (n == 0) ret;
    highs.add(0);
    lows.add(0);
    
    int i = 1;
    while (i < n) {
      // find plateau
      
      var value = values[i];
      int j = i+1;
      while (j < n && values[j] == value) ++j;
      
      // are we going up or down?
      
      var last = values[i-1];
      var list = value > last ? highs : lows;
      
      //if (list.last() == i-1)
      if (values[list.last()] == last)
        list.popLast();
      list.add(i);
      
      i = j;
    }
  }
  
  double get(int idx) { ret values[idx]; }
  
  // returns position of previous high/low
  // or -1 if not found
  int prev(IntBuffer highsOrLows, int idx) {
    int j = intBufferBinarySearch(highsOrLows, idx-1);
    if (j >= 0) ret idx-1;
    j = -j-1;
    j--;
    ret j >= 0 ? highsOrLows.get(j) : -1;
  }
  
  // returns position of next high/low
  // or -1 if not found
  int next(IntBuffer highsOrLows, int idx) {
    int j = intBufferBinarySearch(highsOrLows, idx+1);
    if (j >= 0) ret idx+1;
    j = -j-1;
    ret j < l(highsOrLows) ? highsOrLows.get(j) : -1;
  }
  
  // direction = -1 or 1
  int prevLowerOrHigher(IntBuffer highsOrLows, int idx, int direction) {
    double value = get(idx);
    while (true) {
      int j = prev(highsOrLows, idx);
      if (j < 0 || cmp(get(j), value) == direction) ret j;
      idx = j;
    }
  }
  
  // direction = -1 or 1
  int nextLowerOrHigher(IntBuffer highsOrLows, int idx, int direction) {
    double value = get(idx);
    while (true) {
      int j = next(highsOrLows, idx);
      if (j < 0 || cmp(get(j), value) == direction) ret j;
      idx = j;
    }
  }
  
  // all the prev/next methods return -1 if not found
  
  int prevHigh(int idx) { ret prev(highs, idx); }
  int nextHigh(int idx) { ret next(highs, idx); }
  int prevLow(int idx) { ret prev(lows, idx); }
  int nextLow(int idx) { ret next(lows, idx); }
  
  int prevLowerHigh(int idx) {
    ret prevLowerOrHigher(highs, idx, 1);
  }
  
  int prevLowerLow(int idx) {
    ret prevLowerOrHigher(lows, idx, 1);
  }
  
  int nextLowerHigh(int idx) {
    ret nextLowerOrHigher(highs, idx, 1);
  }
  
  int nextLowerLow(int idx) {
    ret nextLowerOrHigher(lows, idx, 1);
  }
  
  int nextLowOrHigh(int idx) {
    int low = nextLow(idx), high = nextHigh(idx);
    ret high < 0 || low < high ? low : high;
  }
}