# Untitled

unknown
python
a year ago
1.8 kB
0
Indexable
Never
```from sys import stdin
from math import log2, ceil

MOD = 10**9 + 7

sz = 1000001
# 입력 받기

h  = (1<<int(ceil(log2(sz))))

# with open('1.in', 'r') as file:
n = int(input())
nums = list(map(int, input().strip().split()))

tree = [(0,0) for _ in range(4*(sz))] # 길이 개수

def update(idx:int, val):
global h
idx += h
tree[idx] = val
while(1):
idx//=2
if(idx<=0):break
left_leng, left_cnt = tree[idx*2]
right_leng, right_cnt = tree[idx*2+1]
if(left_leng == right_leng):
tree[idx] = (left_leng, (left_cnt + right_cnt)%MOD )
elif left_leng > right_leng:
tree[idx] =  (left_leng, left_cnt)# tree[idx*2]
else:
tree[idx] = (right_leng, right_cnt)# tree[idx*2+1]
return

def query(a:int, b:int):
global h
a += h
b += h
ret = 0
cnt = 0
while(a<=b):
if (a%2==1):
left_leng, left_cnt = tree[a]
if ret == left_leng:
cnt = (cnt + left_cnt) % MOD
elif left_leng > ret:
ret = left_leng
cnt = left_cnt
a+=1
if (b%2==0):
right_leng, right_cnt = tree[b]
if ret == right_leng:
cnt = (cnt + right_cnt) % MOD
elif right_leng > ret:
ret = right_leng
cnt = right_cnt
b-=1
# ret = max(ret, tree[b])
a>>=1
b>>=1

return ret, cnt

# arr = [10, 20, 10, 30, 20, 50]

compress_dict = {num : idx+1 for idx , num in enumerate(sorted(nums))}

for idx, num in enumerate(nums):
best_leg, best_cnt = query(1, num-1)
update(num, (best_leg+1, max(best_cnt,1)))

print(best_leg, best_cnt)

print(tree[1], tree[:30])

```