Нека ни е дадена почетна низа од N цели броеви, и нека почнеме со запишување на првиот број од оваа низа. Потоа, го запишуваме вториот број (лево или десно од првиот), па третиот број (лево или десно од двата досега запишани броеви), па четвртиот број (лево или десно од сите досега запишани броеви) итн. Со ова, може да се добие нова низа од N цели броеви. На пример, ако почетната низа била {10, 20, 30, 4, 5} може да ја добиеме низата {4, 20, 10, 30, 5}, така што прво ќе запишеме 10, потоа 20 лево од него, па 30 десно од двата броја, па 4 лево, па 5 десно.

Во вака добиена низа, може да бараме најдолга растечка подниза (од елементи кои не мора да се последователни), односно најдолгата подниза од броеви така што секој следен број од поднизата е поголем од претходниот. Во {4, 20, 10, 30, 5}, на пример, најдолгата растечка подниза би имала должина три (која било од поднизите {4, 20, 30} и {4, 10, 30}).

Напишете програма која, за дадена почетна низа од N цели броеви, ќе пресмета колку е должината на најдолгата растечка подниза која може да се создаде преку постапката опишана погоре, како и на колку начини може да се стигне до подниза со таа (најголема можна) должина. Видете ги примерите подолу за повеќе информации.

Забелешка: Низа S претставува подниза на низа T, доколку постои начин да се добие S од T преку бришење на одреден број (можеби 0) елементи од низата Т.

Влез

Во првиот ред е запишан еден позитивен цел број N (1 <= N <= 200000), кој го означува бројот на елементи во почетната низа. Во вториот ред се запишани N броеви Ai (1 <= Ai <= 1000000000), кои ги дефинираат вредностите на елементите во почетната низа.

Излез

Во првата линија отпечатете ја должината на најдолгата можна растечка подниза.

Во вториот ред отпечатете го бројот на растечки поднизи со таа должина. Бидејќи овој број може да е многу голем, отпечатете го остатокот при делење на таа вредност со 1000003.

Забелешка: Во тест случаи кои носат најмалку 25% од поените N ≤ 20.

Ограничувања

Временско ограничување: 500 milliseconds
Мемориско ограничување: 64 megabytes

Примери

влез
5
3 2 1 4 5

излез
5
1

влез
3
10 10 10

излез
1
12

влез
4
5 5 7 6

излез
2
20

Објаснување за првиот пример: Најдолгата можна растечка подниза има должина 5, и постои само еден начин да дојдеме до таква подниза. Имено, ако почнеме со 3, па запишеме 2 лево, па 1 лево, па 4 десно, па 5 десно, ќе добиеме {1, 2, 3, 4, 5}. Во овој случај, најдолгата растечка подниза е {1, 2, 3, 4, 5}.

Објаснување за вториот пример: Најдолгата можна растечка подниза има должина 1, и постојат 12 начини на кои може да се направи растечка подниза со должина 1. Имено, по запишување на првата 10-ка, можеме следната да ја запишеме лево или десно, и потоа следната да ја запишеме лево или десно. Значи, постојат четири начини да дојдеме до истата низа {10, 10, 10}. Во ваква низа, најдолгата растечка подниза се состои од еден елемент ({10}), и постојат три начини да се одбере тој елемент (да се земе првата десетка, втората, или третата). Значи, вкупно постојат 3*4=12 начини.