class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int indexDiff, int valueDiff) {
        TreeSet<Integer> window = new TreeSet<>();

        int left = 0, right = 0;

        while (right < nums.length) {
            Integer ceiling = window.ceiling(nums[right]);
            if (ceiling != null && ceiling - nums[right] <= valueDiff) {
                return true;
            }
            Integer floor = window.floor(nums[right]);
            if (floor != null && nums[right] - floor <= valueDiff) {
                return true;
            }


            window.add(nums[right]);
            right++;

            if (right - left > indexDiff) {
                window.remove(nums[left]);
                left++;
            }
        }

        return false;
    }
}

func peakIndexInMountainArray(arr []int) int {
    // 找到 a >= a+1 的最小值
    L, R := 0, len(arr)-1
    for L < R {
        mid := L + (R - L) / 2

        if arr[mid] >= arr[mid+1] {
            R = mid
        } else {
            L = mid + 1
        }
    }

    return L
}

func countTarget(scores []int, target int) int {
    l := leftBound(scores, target)
    if l == len(scores) || scores[l] != target {
        return 0
    }
    r := leftBound(scores, target+1)

    return r - l
}

func leftBound(arr []int, target int) int {
    L, R := 0, len(arr)
    for L < R {
        mid := L + (R - L) / 2
        
        if arr[mid] >= target {
            R = mid
        } else {
            L = mid + 1
        }
    }
    return L
}

func takeAttendance(records []int) int {
    for i, x := range records {
        if i != x {
            return i
        }
    }

    return len(records)
}

func takeAttendance(records []int) int {
    result := 0
    for _, x := range records {
        result ^= x
    }
    for i := 1; i <= len(records); i++ {
        result ^= i
    }
    return result
}

func takeAttendance(records []int) int {
    n := len(records)
    if records[n-1] == n-1 {
        return n
    }

    L, R := 0, n
    for L < R {
        mid := L + (R - L) / 2
        if records[mid] != mid {
            R = mid
        } else {
            L = mid + 1
        }
    }
    return L
}

func search(nums []int, target int) int {
    L, R := 0, len(nums) - 1
    for L <= R {
        mid := L + (R - L) / 2

        if nums[mid] == target {
            return mid
        }

        if nums[mid] >= nums[L] {
            // 此时 L..mid 升序
            if nums[L] <= target && target <= nums[mid] {
                R = mid - 1
            } else {
                L = mid + 1
            }
        } else {
            // 此时 mid..R 升序
            if nums[mid] <= target && target <= nums[R] {
                L = mid + 1
            } else {
                R = mid - 1
            }
        }
    }

    return -1
}

func search(nums []int, target int) bool {
    L, R := 0, len(nums) - 1
    for L <= R {
        for L < R && nums[L] == nums[L+1] {
            L++
        }
        for L < R && nums[R] == nums[R-1] {
            R--
        }

        mid := L + (R - L) / 2

        if nums[mid] == target {
            return true
        }

        if nums[mid] >= nums[L] {
            // 此时 L..mid 升序
            if nums[L] <= target && target <= nums[mid] {
                R = mid - 1
            } else {
                L = mid + 1
            }
        } else {
            // 此时 mid..R 升序
            if nums[mid] <= target && target <= nums[R] {
                L = mid + 1
            } else {
                R = mid - 1
            }
        }
    }

    return false
}