Starry Landscape Photo

AtCoder

IDabc436_f

Time2000ms

Memory256MB

Difficulty—

In the night sky seen from planet AtCoder, there are $N$ stars, and these $N$ stars are arranged in a line from east to west. The $i$\-th star from the east $(1\le i\le N)$ is the $B _ i$\-th brightest among these stars. Takahashi decided to take a picture of the night sky using the following procedure: 1. Choose a pair of integers $(l,r)$ satisfying $1\le l\le r\le N$, and set up the camera so that the $l$\-th, $(l+1)$\-th, $\ldots$, $r$\-th stars from the east all fit in the frame, and no other stars enter the frame. 2. Choose an integer $b$ satisfying $1\le b\le N$, and open the shutter so that all stars among the $N$ stars whose brightness ranks from $1$st through $b$\-th (and that fit in the frame) are captured, and no other stars are captured. However, he may not take a picture with no stars captured. Find the number of different sets of stars that can be captured in pictures taken in this way. ## Constraints * $1\le N\le5\times10 ^ 5$ * $1\le B _ i\le N\ (1\le i\le N)$ * $B _ i\ne B _ j\ (1\le i\lt j\le N)$ * All input values are integers. ## Input The input is given from Standard Input in the following format: $N$ $B _ 1$ $B _ 2$ $\ldots$ $B _ N$ [samples]

Samples

Input #1

4
3 1 4 2

Output #1

12

For example, with $(l,r)=(2,4),b=3$, you can take a picture with two stars: the $2$nd star from the east and the $4$th star from the east.
Including this, you can take pictures with the following $12$ different sets of stars. In each picture, stars further east are arranged further left, and the $i$\-th brightest star is labeled with integer $i$.
![image](https://img.atcoder.jp/abc436/58d5efe8a68a28a223364b9040cb8561.png)
No other sets can be captured, so print `12`.

Input #2

7
1 2 3 4 5 6 7

Output #2

Input #3

20
15 5 13 17 9 11 20 4 14 16 6 3 8 19 12 7 10 18 2 1

Output #3

API Response (JSON)

{
  "problem": {
    "name": "Starry Landscape Photo",
    "description": {
      "content": "In the night sky seen from planet AtCoder, there are $N$ stars, and these $N$ stars are arranged in a line from east to west. The $i$\\-th star from the east $(1\\le i\\le N)$ is the $B _ i$\\-th brightes",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc436_f"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "In the night sky seen from planet AtCoder, there are $N$ stars, and these $N$ stars are arranged in a line from east to west. The $i$\\-th star from the east $(1\\le i\\le N)$ is the $B _ i$\\-th brightes...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments