Untitled

from sys import stdin
from math import log2, ceil

MOD = 10**9 + 7
input = stdin.readline

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])