# Untitled

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

MOD = 10**9 + 7

sz = 1000001
# 입력 받기

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

# 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
idx//=2
while(idx>0):
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]
idx//=2
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]

from math import log2
res = 0
cnt = 0
compress_dict = {num : idx+1 for idx , num in enumerate(sorted(nums))}

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

if(best_leg == 0):
update(num,(1,1))
else:
update(num, (best_leg+1, best_cnt))

if res < best_leg+1:
res = best_leg + 1
# cnt = best_cnt
# num-1 개수 이전 ?
# elif res == best_leg+1:
#     cnt = (cnt + best_cnt)%MOD
print(best_leg, best_cnt)

print(res, tree[:30])

```