FPC25-001.Interesting Mountains

Easy · 2 s · 256 MB

icpc
fpc
2025

On your holiday trip to the mountains, you are amazed by the high quality of your Flashy Yellow Panorama Camera. After shooting a couple of nice photos during your hike, you decide to send the nicest one to your best friend. Sure enough, they immediately reply that they see all kinds of fancy patterns – but they are not talking about the beautiful snow-capped mountains: they have a more abstract view of the photo…

Since the heights of the $n$ mountains in the panorama photo are unique, you can view these heights as a permutation of all numbers between $1$ and $n$ (inclusive). Your friend thinks that a formation of three (not necessarily consecutive) mountains is interesting, when the first mountain is higher than the third mountain, and the third mountain is higher than the second mountain. In other words, three mountains with indices $i$ , $j$ , and $k$ ( $1 \leq i < j < k \leq n$ ) and respective heights $h_i$ , $h_j$ , and $h_k$ are interesting, if and only if $h_i > h_k > h_j$ . How many interesting formations can you find in a given panorama photo?

As an example, consider the first sample input: only the tuples with indices $(1, 3, 5)$ and $(2, 3, 5)$ are interesting formations.

Giriş formatı

The input consists of:

• One line with an integer $n$ ( $3\leq n\leq 3\cdot 10^5$ ), the number of mountains in the photo.

• One line with $n$ integers $h_1,\ldots,h_n$ ( $1\leq h_i\leq n$ for each $i$ ), the heights of the mountains in the photo. It is guaranteed all values of $h_i$ are unique.

Çıxış formatı

Output the number of interesting formations in the panorama photo.

Qeyd

Source: Freshmen Programming Contest 2025 · License: CC BY-SA 4.0 · Original: https://fpc.wisv.ch · Statement adapted for AlgoLens and shared under the same license. · 14 of the 37 original test cases (the largest) are omitted here to keep the problem lightweight.

Nümunələr

Giriş #1

5
3 4 1 5 2

Çıxış #1

Giriş #2

3
3 1 2

Çıxış #2

Giriş #3

3
2 1 3

Çıxış #3

Giriş #4

11
5 9 10 11 1 2 3 4 6 7 8

Çıxış #4

Giriş formatı

The input consists of:

• One line with an integer $n$ ( $3\leq n\leq 3\cdot 10^5$ ), the number of mountains in the photo.

• One line with $n$ integers $h_1,\ldots,h_n$ ( $1\leq h_i\leq n$ for each $i$ ), the heights of the mountains in the photo. It is guaranteed all values of $h_i$ are unique.