## https://yukicoder.me/problems/no/1864 MOD = 998244353 class SegmentTree: """ 非再帰版セグメント木。 更新は「加法」、取得は「最大値」のもの限定。 """ def __init__(self, init_array): n = 1 while n < len(init_array): n *= 2 self.size = n self.array = [0] * (2 * self.size) for i, a in enumerate(init_array): self.array[self.size + i] = a end_index = self.size start_index = end_index // 2 while start_index >= 1: for i in range(start_index, end_index): self.array[i] = self.array[2 * i] + self.array[2 * i + 1] self.array[i] %= MOD end_index = start_index start_index = end_index // 2 def add(self, x, a): index = self.size + x self.array[index] += a self.array[index] %= MOD while index > 1: index //= 2 self.array[index] = self.array[2 * index] + self.array[2 * index + 1] self.array[index] %= MOD def get_sum(self, l, r): L = self.size + l; R = self.size + r # 2. 区間[l, r)の最大値を求める s = 0 while L < R: if R & 1: R -= 1 s += self.array[R] s %= MOD if L & 1: s += self.array[L] s %= MOD L += 1 L >>= 1; R >>= 1 return s def main(): N = int(input()) xy = [] for _ in range(N): x, y = map(int, input().split()) xy.append((x, y)) # チェビシェフ変換 -> マンハッタン距離 * 2 の世界で考える uv = [] for x, y in xy: u = x + y v = x - y uv.append([u, v]) # u0 < uN, v0 < vNの世界で考えても問題ないように標準化する if uv[0][0] > uv[-1][0]: for i in range(N): uv[i][0] *= -1 if uv[0][1] > uv[-1][1]: for i in range(N): uv[i][1] *= -1 # u0 <= uN, v0 <= vNの中にいる点だけ取り出す uv2 = [] for u, v in uv: if uv[0][0] <= u <= uv[-1][0] and uv[0][1] <= v <= uv[-1][1]: uv2.append((u, v)) # uベースでまとめる u_map = {} for u, v in uv2: if u not in u_map: u_map[u] = [] u_map[u].append(v) # vベースでの座標圧縮 v_set = set() for _, v in uv2: v_set.add(v) v_list = list(v_set) v_list.sort() v_map = {} for i, v in enumerate(v_list): v_map[v] = i v_max = len(v_list) # 平面捜査による解法で実施 seg_tree = SegmentTree([0] * v_max) u_array = [(u, v_array) for u, v_array in u_map.items()] u_array.sort(key=lambda x : x[0]) ans = -1 for u, v_array in u_array: v_array.sort() for v in v_array: if (u, v) == uv2[0]: seg_tree.add(0, 1) else: x = seg_tree.get_sum(0, v_map[v] + 1) ans = x seg_tree.add(v_map[v], x) print(ans) if __name__ == '__main__': main()