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

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