По завршувањето на минатогодишниот Државен натпревар по информатика, организаторите ги замолиле натпреварувачите да се наредат еден до друг (во една редица) и заедно да се сликаат. Еден натпреварувач (ќе го викаме Ирвас), кој имал многу слаб резултат, решил, менувајќи ја оригиналната слика, да направи нова слика која ќе ја нарече "Аптекарски шишиња". Тоа е слика на која има тројца од натпреварувачите на почетната слика, при што првиот (најлевиот) е највисок, вториот понизок и третиот (најдесниот) е најнизок.

Ирвас, покрај тоа што не го бивало баш за програмирање, не умеел и којзнае како да обработува слики, па единствено што можел да направи е да отстрани одредени учесници од сликата и другите да ги збие за да изгледа како тие да се еден до друг.

На пример, ако сликата со натпреварувачите изгледа вака ABCDEFGHIJK (една буква, еден натпреварувач) тогаш тој може да ги добие, на пример, следниве "обработени" слики: ABC, ABD, BFG, CFH итн. Дополнително, тој мора да внимава на висините, првиот да е повисок од вториот, а вториот да е повисок од третиот.

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

Влез

Во првиот ред е запишан еден цел број N (3 <= N <= 100000), кој го означува бројот на натпреварувачи. Во втората линија се запишани N цели броеви Ri (1 <= Ri <= 1000000000), кои ги означуваат висините на секој од N-те натпреварувачи - почнувајќи со висината R1 на натпреварувачот кој е најлево на сликата, па резултатот R2 на натпреварувачот кој застанал веднаш десно од него (значи втор), итн. Не постојат два натпреварувачи со иста висина.

Излез

Излезот се состои од еден ред во кој треба да го отпечатите бараниот резултат. Бројот на можни фотографии може да е мнооогу голем број - користeте тип на податок кој поддржува чување на 64-битни цели броеви, како int64 и qword во Pascal, или long long во C/C++.

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

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

Примери

влез
4
190 180 170 168

излез
4

влез
3
190 192 184

излез
0

влез
4
170 180 190 200

излез
0

Објаснување за првиот пример: Тројките се (190, 180, 170), (190, 180, 168), (190, 170, 168) и (180, 170, 168).