Codeforces Round #804 (Div. 2)
5 өдрийн дараа |
C. Сэрэжа ба дэд дараалал
хугацааны хязгаарлалт 2 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Сэрэжад $n$ урттай эерэг бүхэл тоон дараалал $a_{1}, a_{2}, ..., a_{n}$ өгөгджээ.
Эхлээд Сэрэжа дөрвөлжин цаасан дээр $a$-ийн бүх ялгаатай, хоосон биш, үл буурах дэд дарааллуудыг бичжээ. Тэгээд цаасан дээрх дараалал тус бүрт харгалзуулан түүнээс хэтрэхгүй бүх дарааллуудыг туузан цааснууд дээр бичжээ.
$x_{1} ≤ y_{1}, x_{2} ≤ y_{2}, ..., x_{r} ≤ y_{r}$ нөхцөл биелж байвал эерэг тоон дараалал $x = x_{1}, x_{2}, ..., x_{r}$ нь эерэг тоон дараалал $y = y_{1}, y_{2}, ..., y_{r}$-ээс хэтрэхгүй гэж ойлгоно.
Одоо Сэрэжа хичнээн дараалал туузан цааснууд дээр бичигдсэнийг мэдэхийг хүсжээ. Хариуг $1000000007$ $(10^{9}+7)$ тоонд хуваан үлдэгдлийг олно уу.
Оролт
Эхний мөрөнд бүхэл тоо $n$ $(1 ≤ n ≤ 10^{5})$ байна. Хоёр дахь мөрөнд $a_{1}, a_{2}, ..., a_{n}$ $(1 ≤ a_{i} ≤ 10^{6})$ гэсэн $n$ ширхэг бүхэл тоонууд байна.
Гаралт
Хариуг $1000000007$ $(10^{9} + 7)$ тоонд хуваан хэвлэ.
Орчуулсан: Бат-Од
Жишээ тэстүүд
Оролт
1 42
Гаралт
42
Оролт
3 1 2 2
Гаралт
13
Оролт
5 1 2 3 4 5
Гаралт
719