```html
<!DOCTYPE html>
<html class="no-js" lang="zh">
<head>
    <meta charset="utf-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <title>[COI2007] Patrik 音乐会的等待 - 洛谷</title>
    <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1, user-scalable=no">
    <meta name="renderer" content="webkit">
        <meta name="csrf-token" content="1708743054:9AZGqhlpTTsUB96Z9AttEJicW8ilRHHSJG+RjousC1c=">
        <meta http-equiv="Content-Security-Policy" content="default-src 'unsafe-inline' luogu.com.cn *.luogu.com.cn luogu.org *.luogu.org *.cnzz.com luoguprivate.oss-cn-hangzhou.aliyuncs.com luogu.oss-cn-hangzhou.aliyuncs.com wss: blob:; img-src * data:; font-src * data:; frame-src https://player.bilibili.com https://www.bilibili.com">
        <link rel="shortcut icon" type="image/x-icon" href="/favicon.ico" media="screen"/>
    <link rel="stylesheet" href="https://fecdn.luogu.com.cn/luogu/loader.css?ver=20240206">
    <script>window._feInjection = JSON.parse(decodeURIComponent("%7B%22code%22%3A200%2C%22currentTemplate%22%3A%22ProblemShow%22%2C%22currentData%22%3A%7B%22problem%22%3A%7B%22background%22%3A%22%22%2C%22description%22%3A%22%24n%24%20%5Cu4e2a%5Cu4eba%5Cu6b63%5Cu5728%5Cu6392%5Cu961f%5Cu8fdb%5Cu5165%5Cu4e00%5Cu4e2a%5Cu97f3%5Cu4e50%5Cu4f1a%5Cu3002%5Cu4eba%5Cu4eec%5Cu7b49%5Cu5f97%5Cu5f88%5Cu65e0%5Cu804a%5Cuff0c%5Cu4e8e%5Cu662f%5Cu4ed6%5Cu4eec%5Cu5f00%5Cu59cb%5Cu8f6c%5Cu6765%5Cu8f6c%5Cu53bb%5Cuff0c%5Cu60f3%5Cu5728%5Cu961f%5Cu4f0d%5Cu91cc%5Cu5bfb%5Cu627e%5Cu81ea%5Cu5df1%5Cu7684%5Cu719f%5Cu4eba%5Cu3002%5Cn%5Cn%5Cu961f%5Cu5217%5Cu4e2d%5Cu4efb%5Cu610f%5Cu4e24%5Cu4e2a%5Cu4eba%20%24a%24%20%5Cu548c%20%24b%24%5Cuff0c%5Cu5982%5Cu679c%5Cu4ed6%5Cu4eec%5Cu662f%5Cu76f8%5Cu90bb%5Cu6216%5Cu4ed6%5Cu4eec%5Cu4e4b%5Cu95f4%5Cu6ca1%5Cu6709%5Cu4eba%5Cu6bd4%20%24a%24%20%5Cu6216%20%24b%24%20%5Cu9ad8%5Cuff0c%5Cu90a3%5Cu4e48%5Cu4ed6%5Cu4eec%5Cu662f%5Cu53ef%5Cu4ee5%5Cu4e92%5Cu76f8%5Cu770b%5Cu5f97%5Cu89c1%5Cu7684%5Cu3002%5Cn%5Cn%5Cu5199%5Cu4e00%5Cu4e2a%5Cu7a0b%5Cu5e8f%5Cu8ba1%5Cu7b97%5Cu51fa%5Cu6709%5Cu591a%5Cu5c11%5Cu5bf9%5Cu4eba%5Cu53ef%5Cu4ee5%5Cu4e92%5Cu76f8%5Cu770b%5Cu89c1%5Cu3002%22%2C%22inputFormat%22%3A%22%5Cu8f93%5Cu5165%5Cu7684%5Cu7b2c%5Cu4e00%5Cu884c%5Cu5305%5Cu542b%5Cu4e00%5Cu4e2a%5Cu6574%5Cu6570%20%24n%24%5Cuff0c%5Cu8868%5Cu793a%5Cu961f%5Cu4f0d%5Cu4e2d%5Cu5171%5Cu6709%20%24n%24%20%5Cu4e2a%5Cu4eba%5Cu3002%5Cn%5Cn%5Cu63a5%5Cu4e0b%5Cu6765%5Cu7684%20%24n%24%20%5Cu884c%5Cu4e2d%5Cuff0c%5Cu6bcf%5Cu884c%5Cu5305%5Cu542b%5Cu4e00%5Cu4e2a%5Cu6574%5Cu6570%5Cuff0c%5Cu8868%5Cu793a%5Cu4eba%5Cu7684%5Cu9ad8%5Cu5ea6%5Cuff0c%5Cu4ee5%5Cu6beb%5Cu5fae%5Cu7c73%28%5Cu7b49%5Cu4e8e%20%2410%5E%7B-9%7D%24%20%5Cu7c73%29%5Cu4e3a%5Cu5355%5Cu4f4d%5Cuff0c%5Cu8fd9%5Cu4e9b%5Cu9ad8%5Cu5ea6%5Cu5206%5Cu522b%5Cu8868%5Cu793a%5Cu961f%5Cu4f0d%5Cu4e2d%5Cu4eba%5Cu7684%5Cu8eab%5Cu9ad8%5Cu3002%22%2C%22outputFormat%22%3A%22%5Cu8f93%5Cu51fa%5Cu4ec5%5Cu6709%5Cu4e00%5Cu884c%5Cuff0c%5Cu5305%5Cu542b%5Cu4e00%5Cu4e2a%5Cu6570%20%24s%24%5Cuff0c%5Cu8868%5Cu793a%5Cu961f%5Cu4f0d%5Cu4e2d%5Cu5171%5Cu6709%20%24s%24%20%5Cu5bf9%5Cu4eba%5Cu53ef%5Cu4ee5%5Cu4e92%5Cu76f8%5Cu770b%5Cu89c1%5Cu3002%22%2C%22samples%22%3A%5B%5B%227%20%5Cn2%20%5Cn4%20%5Cn1%20%5Cn2%20%5Cn2%20%5Cn5%20%5Cn1%22%2C%2210%22%5D%5D%2C%22hint%22%3A%22%23%23%23%23%20%5Cu6570%5Cu636e%5Cu89c4%5Cu6a21%5Cu4e0e%5Cu7ea6%5Cu5b9a%5Cn%5Cu5bf9%5Cu4e8e%5Cu5168%5Cu90e8%5Cu7684%5Cu6d4b%5Cu8bd5%5Cu70b9%5Cuff0c%5Cu4fdd%5Cu8bc1%20%241%5C%5Cle%24%20%5Cu6bcf%5Cu4e2a%5Cu4eba%5Cu7684%5Cu9ad8%5Cu5ea6%20%24%3C%202%5E%7B31%7D%24%5Cuff0c%241%20%5C%5Cle%20n%20%5C%5Cle%205%5C%5Ctimes%2010%5E5%24%5Cu3002%22%2C%22provider%22%3A%7B%22uid%22%3A254%2C%22name%22%3A%22JosephZheng%22%2C%22avatar%22%3A%22https%3A%5C%2F%5C%2Fcdn.luogu.com.cn%5C%2Fupload%5C%2Fusericon%5C%2F254.png%22%2C%22slogan%22%3Anull%2C%22badge%22%3Anull%2C%22isAdmin%22%3Afalse%2C%22isBanned%22%3Afalse%2C%22color%22%3A%22Gray%22%2C%22ccfLevel%22%3A0%2C%22background%22%3A%22%22%7D%2C%22attachments%22%3A%5B%5D%2C%22canEdit%22%3Afalse%2C%22limits%22%3A%7B%22time%22%3A%5B1000%2C1000%2C1000%2C1000%2C1000%2C1000%2C1000%2C1000%2C1000%2C1000%2C1000%2C1000%2C1000%2C1000%2C1000%2C1000%2C1000%2C1000%2C1000%2C1000%2C1000%2C1000%2C1000%5D%2C%22memory%22%3A%5B128000%2C128000%2C128000%2C128000%2C128000%2C128000%2C128000%2C128000%2C128000%2C128000%2C128000%2C128000%2C128000%2C128000%2C128000%2C128000%2C128000%2C128000%2C128000%2C128000%2C128000%2C128000%2C128000%5D%7D%2C%22showScore%22%3Atrue%2C%22score%22%3Anull%2C%22stdCode%22%3A%22%22%2C%22tags%22%3A%5B1%2C24%2C44%2C287%2C333%5D%2C%22wantsTranslation%22%3Afalse%2C%22totalSubmit%22%3A28493%2C%22totalAccepted%22%3A6924%2C%22flag%22%3A5%2C%22pid%22%3A%22P1823%22%2C%22title%22%3A%22%5BCOI2007%5D%20Patrik%20%5Cu97f3%5Cu4e50%5Cu4f1a%5Cu7684%5Cu7b49%5Cu5f85%22%2C%22difficulty%22%3A4%2C%22fullScore%22%3A100%2C%22type%22%3A%22P%22%2C%22accepted%22%3Afalse%2C%22submitted%22%3Afalse%7D%2C%22contest%22%3Anull%2C%22discussions%22%3A%5B%7B%22id%22%3A768218%2C%22title%22%3A%2220%5Cu5206%5Cu6c42%5Cu52a9%5Cuff0c%5Cu60ac%5Cu5173%22%2C%22forum%22%3A%7B%22id%22%3A875%2C%22name%22%3A%22P1823%20%5BCOI2007%5D%20Patrik%20%5Cu97f3%5Cu4e50%5Cu4f1a%5Cu7684%5Cu7b49%5Cu5f85%22%2C%22slug%22%3A%22P1823%22%7D%7D%2C%7B%22id%22%3A748368%2C%22title%22%3A%22%5Cu4e3a%5Cu4ec0%5Cu4e48%22%2C%22forum%22%3A%7B%22id%22%3A875%2C%22name%22%3A%22P1823%20%5BCOI2007%5D%20Patrik%20%5Cu97f3%5Cu4e50%5Cu4f1a%5Cu7684%5Cu7b49%5Cu5f85%22%2C%22slug%22%3A%22P1823%22%7D%7D%2C%7B%22id%22%3A748360%2C%22title%22%3A%22%3C%5Cu770b%5Cu4e0d%5Cu61c2%3E%22%2C%22forum%22%3A%7B%22id%22%3A875%2C%22name%22%3A%22P1823%20%5BCOI2007%5D%20Patrik%20%5Cu97f3%5Cu4e50%5Cu4f1a%5Cu7684%5Cu7b49%5Cu5f85%22%2C%22slug%22%3A%22P1823%22%7D%7D%2C%7B%22id%22%3A748334%2C%22title%22%3A%22%5Cu8b66%5Cu793a%5Cu540e%5Cu4eba%22%2C%22forum%22%3A%7B%22id%22%3A875%2C%22name%22%3A%22P1823%20%5BCOI2007%5D%20Patrik%20%5Cu97f3%5Cu4e50%5Cu4f1a%5Cu7684%5Cu7b49%5Cu5f85%22%2C%22slug%22%3A%22P1823%22%7D%7D%2C%7B%22id%22%3A747556%2C%22title%22%3A%22%5Cu5355%5Cu8c03%5Cu6808%5Cuff0c%5Cu6c42%5Cu538b%5Cu7f29%5Cu65f6%5Cu95f4%5Cu590d%5Cu6742%5Cu5ea6%22%2C%22forum%22%3A%7B%22id%22%3A875%2C%22name%22%3A%22P1823%20%5BCOI2007%5D%20Patrik%20%5Cu97f3%5Cu4e50%5Cu4f1a%5Cu7684%5Cu7b49%5Cu5f85%22%2C%22slug%22%3A%22P1823%22%7D%7D%2C%7B%22id%22%3A737972%2C%22title%22%3A%22%5Cu5fc5%5Cu987b%5Cu624b%5Cu6413%5Cu6808%5Cuff1f%22%2C%22forum%22%3A%7B%22id%22%3A875%2C%22name%22%3A%22P1823%20%5BCOI2007%5D%20Patrik%20%5Cu97f3%5Cu4e50%5Cu4f1a%5Cu7684%5Cu7b49%5Cu5f85%22%2C%22slug%22%3A%22P1823%22%7D%7D%5D%2C%22bookmarked%22%3Atrue%2C%22vjudgeUsername%22%3Anull%2C%22recommendations%22%3A%5B%7B%22pid%22%3A%22P1725%22%2C%22title%22%3A%22%5Cu742a%5Cu9732%5Cu8bfa%22%2C%22difficulty%22%3A4%2C%22fullScore%22%3A200%2C%22type%22%3A%22P%22%2C%22accepted%22%3Afalse%2C%22submitted%22%3Afalse%7D%2C%7B%22pid%22%3A%22P1886%22%2C%22title%22%3A%22%5Cu6ed1%5Cu52a8%5Cu7a97%5Cu53e3%20%5C%2F%5Cu3010%5Cu6a21%5Cu677f%5Cu3011%5Cu5355%5Cu8c03%5Cu961f%5Cu5217%22%2C%22difficulty%22%3A3%2C%22fullScore%22%3A200%2C%22type%22%3A%22P%22%2C%22accepted%22%3Afalse%2C%22submitted%22%3Afalse%7D%2C%7B%22pid%22%3A%22P1901%22%2C%22title%22%3A%22%5Cu53d1%5Cu5c04%5Cu7ad9%22%2C%22difficulty%22%3A3%2C%22fullScore%22%3A100%2C%22type%22%3A%22P%22%2C%22accepted%22%3Afalse%2C%22submitted%22%3Afalse%7D%2C%7B%22pid%22%3A%22P2569%22%2C%22title%22%3A%22%5BSCOI2010%5D%20%5Cu80a1%5Cu7968%5Cu4ea4%5Cu6613%22%2C%22difficulty%22%3A6%2C%22fullScore%22%3A100%2C%22type%22%3A%22P%22%2C%22accepted%22%3Afalse%2C%22submitted%22%3Afalse%7D%2C%7B%22pid%22%3A%22P3957%22%2C%22title%22%3A%22%5BNOIP2017%20%5Cu666e%5Cu53ca%5Cu7ec4%5D%20%5Cu8df3%5Cu623f%5Cu5b50%22%2C%22difficulty%22%3A4%2C%22fullScore%22%3A100%2C%22type%22%3A%22P%22%2C%22accepted%22%3Afalse%2C%22submitted%22%3Afalse%7D%5D%2C%22lastLanguage%22%3A28%2C%22lastCode%22%3A%22%22%2C%22privilegedTeams%22%3A%5B%7B%22id%22%3A29747%2C%22name%22%3A%22%5Cu7701%5Cu5b9e%5Cu521d%5Cu4e00%5Cu4fe1%5Cu606f%5Cu5b66%5Cu56e2%5Cu961f%22%2C%22isPremium%22%3Afalse%7D%2C%7B%22id%22%3A46832%2C%22name%22%3A%22%5Cu7701%5Cu5b9e%5Cu9ec4%5Cu961f%5Cu8bde%5Cu751f%5Cu4e86%22%2C%22isPremium%22%3Afalse%7D%2C%7B%22id%22%3A35046%2C%22name%22%3A%22hjhAKIOI%22%2C%22isPremium%22%3Afalse%7D%5D%2C%22userTranslation%22%3Anull%7D%2C%22currentTitle%22%3A%22%5BCOI2007%5D%20Patrik%20%5Cu97f3%5Cu4e50%5Cu4f1a%5Cu7684%5Cu7b49%5Cu5f85%22%2C%22currentTheme%22%3A%7B%22id%22%3A1%2C%22header%22%3A%7B%22imagePath%22%3Anull%2C%22color%22%3A%5B%5B35%2C37%2C38%2C1%5D%2C%5B65%2C67%2C69%2C1%5D%5D%2C%22blur%22%3A0%2C%22brightness%22%3A0%2C%22degree%22%3A90%2C%22repeat%22%3A0%2C%22position%22%3A%5B50%2C50%5D%2C%22size%22%3A%5B0%2C0%5D%2C%22type%22%3A2%2C%22__CLASS_NAME%22%3A%22Luogu%5C%5CDataClass%5C%5CUser%5C%5CThemeConfig%5C%5CHeaderFooterConfig%22%7D%2C%22sideNav%22%3A%7B%22logoBackgroundColor%22%3A%5B52%2C152%2C219%2C1%5D%2C%22color%22%3A%5B52%2C73%2C94%2C1%5D%2C%22invertColor%22%3Afalse%2C%22__CLASS_NAME%22%3A%22Luogu%5C%5CDataClass%5C%5CUser%5C%5CThemeConfig%5C%5CSideNavConfig%22%7D%2C%22footer%22%3A%7B%22imagePath%22%3Anull%2C%22color%22%3A%5B%5B51%2C51%2C51%2C1%5D%5D%2C%22blur%22%3A0%2C%22brightness%22%3A0%2C%22degree%22%3A0%2C%22repeat%22%3A0%2C%22position%22%3A%5B0%2C0%5D%2C%22size%22%3A%5B0%2C0%5D%2C%22type%22%3A2%2C%22__CLASS_NAME%22%3A%22Luogu%5C%5CDataClass%5C%5CUser%5C%5CThemeConfig%5C%5CHeaderFooterConfig%22%7D%7D%2C%22currentTime%22%3A1708656654%2C%22currentUser%22%3A%7B%22followingCount%22%3A31%2C%22followerCount%22%3A20%2C%22ranking%22%3A5572%2C%22eloValue%22%3A614%2C%22blogAddress%22%3A%22https%3A%5C%2F%5C%2Fwww.luogu.com.cn%5C%2Fblog%5C%2Fadpitac-chen%5C%2F%22%2C%22unreadMessageCount%22%3A0%2C%22unreadNoticeCount%22%3A0%2C%22uid%22%3A374733%2C%22name%22%3A%22adpitacor%22%2C%22avatar%22%3A%22https%3A%5C%2F%5C%2Fcdn.luogu.com.cn%5C%2Fupload%5C%2Fusericon%5C%2F374733.png%22%2C%22slogan%22%3A%22%5Cu8fd9%5Cu4e2a%5Cu4eba%5Cu2026%5Cu2026%22%2C%22badge%22%3Anull%2C%22isAdmin%22%3Afalse%2C%22isBanned%22%3Afalse%2C%22color%22%3A%22Orange%22%2C%22ccfLevel%22%3A7%2C%22background%22%3A%22%22%2C%22verified%22%3Atrue%7D%7D"));window._feConfigVersion=1707298564;window._tagVersion=1708654735;</script>
    <script src="https://fecdn.luogu.com.cn/luogu/loader.js?ver=20240206" charset="utf-8" defer></script>
</head>
<body>
<div id="app">
    <div class="lg-container">
        <!-- SEO -->
<article>
    <h1>[COI2007] Patrik 音乐会的等待</h1>

    
    
    <h2>题目描述</h2>
    <div>$n$ 个人正在排队进入一个音乐会。人们等得很无聊，于是他们开始转来转去，想在队伍里寻找自己的熟人。

队列中任意两个人 $a$ 和 $b$，如果他们是相邻或他们之间没有人比 $a$ 或 $b$ 高，那么他们是可以互相看得见的。

写一个程序计算出有多少对人可以互相看见。</div>

    <h2>输入输出格式</h2>
    <h3>输入格式</h3>
    <br />
    <div>输入的第一行包含一个整数 $n$，表示队伍中共有 $n$ 个人。

接下来的 $n$ 行中，每行包含一个整数，表示人的高度，以毫微米(等于 $10^{-9}$ 米)为单位，这些高度分别表示队伍中人的身高。</div>
    <h3>输出格式</h3>
    <br />
    <div>输出仅有一行，包含一个数 $s$，表示队伍中共有 $s$ 对人可以互相看见。</div>

    <h2>输入输出样例</h2>
                        <h3>输入样例 #1</h3>
            <pre><code>7 
2 
4 
1 
2 
2 
5 
1</code></pre>
            <h3>输出样例 #1</h3>
            <pre><code>10</code></pre>
            
            <h2>说明</h2>
        <div>#### 数据规模与约定
对于全部的测试点，保证 $1\le$ 每个人的高度 $&lt; 2^{31}$，$1 \le n \le 5\times 10^5$。</div>
    </article>
    </div>
</div>
<!-- <script src="//www.recaptcha.net/recaptcha/api.js?hl=zh-CN&render=explicit&onload=renderCaptcha" async defer></script> -->
</body>
</html>
```