== include(page="template/taskheader" task_id="subsir100") ==

Poveste şi cerinţă...

Andreea a primit de la prietena sa Ioana un sir format din $N$ numere naturale. Deoarece Ioanei ii plac subsirurile "interesante", ea a rugat-o pe Andreea sa numere cate subsiruri "interesante" contine sirul de numere. Un subsir este "interesant" daca contine doar numere distincte. Pentru ca numarul de subsiruri interesante poate fi mare, Andreea va cere sa aflati doar restul impartirii acestui numar la $1000003$.

h2. Date de intrare

Fişierul de intrare $subsir100.in$ ...

Fişierul de intrare $subsir100.in$ contine pe prima linie un numar natural $N$, avand semnificatia din enunt. Pe urmatoarea linie se afla $N$ numere naturale, separate de cate un singur spatiu reprezentand sirul de numere.

h2. Date de ieşire

În fişierul de ieşire $subsir100.out$ ...

În fişierul de ieşire $subsir100.out$ se va afla numarul total de subsiruri "interesante", modulo $1000003$.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 100 000$
* Numere din sir sunt numere naturale mai mici decat $2 000 000 000$.
* Considerand ca sirul dat este {$A=(a{~1~},a{~2~}...a{~N~})$}, se numeste subsir al lui $A$ un sir {$B=(b{~i{~1~}~},b{~i{~2~}~}...b{~i{~N~}~})$} cu proprietatea $1 &le; i{~1~} < i{~2~} < ... < i{~K~} &le; N$.

h2. Exemplu
table(example). |_. subsir100.in |_. subsir100.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 3
  1 1 2
| 5

|
h3. Explicaţie

...

Cele $5$ subsiruri distincte sunt: $1$, $2$, $1 1$, $1 2$ si $1 1 2$.

== include(page="template/taskfooter" task_id="subsir100") ==