Hoán vị con

Submit solution
Points: 2 (partial)
Time limit: 1.0s
Memory limit: 67M
Author:
old_creator
Problem type
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG

Một hoán vị cỡ \(n\) là một dãy số gồm \(n\) phần tử đôi một phân biệt từ \(1\) tới \(n\).

Ví dụ: \((1, 2, 3, 4)\) là hoán vị cỡ \(4\) , \((5, 2, 1, 3, 4)\) là hoán vị cỡ \(5\). \((1, 1, 2, 3)\), \((2, 3, 4, 5)\) không là hoán vị.

Cho một dãy số là hoán vị cỡ \(n\), bạn hãy đếm số đoạn con từ dãy số đã cho mà cũng là hoán vị.

Ghi chú: Đoạn con là dãy con chứa các phần tử liên tiếp, dãy số \((a)\) có các đoạn con dạng \(a_l, a_{l + 1}, ..., a_{r}\).

Đầu vào

Dòng đầu tiên chứa só tự nhiên \(n\) \((1 \le n \le 10^6)\), số phần tử trong dãy số

Dòng thứ hai chứa \(n\) số tự nhiên đôi một phân biệt trong khoảng \([1, n]\) là các phần tử của dãy số.

Đầu ra

Một số tự nhiên duy nhất là số dãy con thỏa mãn đề bài.

Subtask

\(30\%\) số test có \(n \le 100\).

\(30\%\) số test có số \(1\) đứng ở vị trí đầu tiên.

Ví dụ

Đầu vào 1:

4
1 2 3 4

Đầu ra 1:

4

Giải thích: \((1), (1, 2), (1, 2, 3), (1, 2, 3, 4)\) là các hoán vị con của dãy số.

Đầu vào 2:

4
2 1 4 3

Đầu ra 2:

3

Giải thích: \((1), (2, 1), (2, 1, 4, 3)\) là các hoán vị con của dãy số.

QDUY

Comments