def compress(array): """座標圧縮したリストを返す""" array2 = sorted(set(array)) memo = {value: index for index, value in enumerate(array2)} for i in range(len(array)): array[i] = memo[array[i]] return array class SegmentTree(): """一点加算、区間取得クエリをそれぞれO(logN)で答えるデータ構造を構築する add: i番目にvalをmergeする get_sum: 区間[begin, end)のmergeの結果を求める (最大値, 最大値の個数)のペアはモノイドになる、すごい 単位元は(0, 1) であってる? 演算についてはmergeを参照 """ def __init__(self, n): self.n = n self.size = 1 while self.size < n: self.size *= 2 self.node = [(0, 1)] * (2*self.size - 1) def add(self, i, val): i += (self.size - 1) self.node[i] = self.merge(self.node[i], val) while i > 0: i = (i - 1) // 2 self.node[i] = self.merge(self.node[2*i + 1], self.node[2*i + 2]) def get_sum(self, begin, end): begin += (self.size - 1) end += (self.size - 1) s = (0, 1) while begin < end: if (end - 1) & 1: end -= 1 s = self.merge(s, self.node[end]) if (begin - 1) & 1: s = self.merge(s, self.node[begin]) begin += 1 begin = (begin - 1) // 2 end = (end - 1) // 2 return s def merge(self, a, b): """マージする""" max_a, cnt_a = a max_b, cnt_b = b if max_a > max_b: return (max_a, cnt_a) elif max_a < max_b: return (max_b, cnt_b) if max_a == 0: return (0, 1) return (max_a, (cnt_a + cnt_b) % MOD) n = int(input()) a = list(map(int, input().split())) a = compress(a) MOD = 10 ** 9 + 7 st = SegmentTree(n) for num in a: max_, cnt = st.get_sum(0, num) st.add(num, (max_ + 1, cnt)) print(st.get_sum(0, n)[1] % MOD)