Migrated from Lutece 2536 异地恋

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

上个世纪 $90$ 年代，虽然交通不像现在这么发达，但是仍然有着许多执着于爱情的异地恋小青年，小明和小红就是这样一对情侣。高中毕业那年，由于小明太强了，考上了一个比小红更厉害的学校，于是他们不得不开始异地恋。一年有 $365$ 天，不见面的日子小明都思念着小红，于是小明决定每个月都坐火车去见一次小红。

就这样，每个月的最后一个周末，小红都在火车站的出口迎接小明的到来。这个火车站非常大，并且有非常多的小型出口，每个出口都有一个编号，这些编号可能是重复的，这是因为相同编号的小型出口归同一个火车站的负责人管理。

这些出口都是从地底下延伸到地面上的，开口向南，就像现在的地铁的出口一样，它们就这样紧密的排成一条直线（由于特别紧密，每个人的位置都可以用某个出口所在的位置来表示），从北向南，其中最北方对应的是火车站的最里面，最南方对应的是离开整个火车站的出口。

为了和小明见面，小红每次都会随机选择一个出口作为起点，然后面朝北方，等待小明的出现。由于种种原因，小明总是随机的从某个出口中走出来，并一直向南笔直地走，不会回头看北方，因为他脖子经常落枕，没办法回头，这导致小红不总是能够见到小明。当然，小红为了快点见到小明，她不总是傻傻地等在原地，而是会时不时朝北走去，因为她觉得当前出口可能没有小明。然而火车站有时候特别拥挤，即使小红和小明相遇了，他们不一定能迅速看到对方。

火车站的负责人也深知情侣无法相见的这种痛苦，于是他们提供了免费的情侣见面帮助服务，每对情侣只需要去登记就可以在每次火车站见面的时候享受这种服务，小红和小明为了减少每次见面时的痛苦，他们也将自己登记到了这种服务上。具体来说，火车站给每个小型出口都安装了监控系统，相同编号的小型出口被同一个保安监管，并且这些保安非常的负责，能够洞察他负责的所有小型出口的情况。为了减少工作量，每个保安都只对那些经过他所负责的小型出口两次的人产生特别关注，因为这些人很可能是在寻找他的另一半。当然，保安是知道这些特别关注名单上的所有人对应的另一半是谁，毕竟都是登记过的。

以小红为例，当保安把小红纳入特别关注名单以后，保安会盯着他负责的所有小型出口中被小红经过的那些出口，首先保安会调取监控记录看小明是否在之前已经经过了这些出口中的任意一个，只要小明之前经过这些出口中的任意一个，那么火车站就会发起广播，呼叫小明和小红，并公布小明和小红的位置，如果小明之前没有经过这些出口，那么保安会继续监控这些被小红经过的出口（当然小红可能一直在走动，这些监控的出口名单也可能持续增加），直到小明经过，就发起广播让他们两个见面。小明和小红一旦听到就会立刻转身向与刚才行进相反的方向行进，即小明向北，小红向南。

小红和小明见面后会互相分享着在刚才路上的所见所闻（分享一些类似「我刚才经过了某些位置的出口」的话），不过有可能某一方经过的出口都被另一方给经过了，这样两个人就少了一些交谈的乐趣，这样的见面并不是完美的，当然如果两人能够见面并且还能愉快地分享路上的所见所闻（即每个人都经过了对方不能经过的出口位置），只要这次见面与以前的所有见面都不同（两次见面相同当且仅当两次见面对应的两个人的行进经过的出口位置构成的集合完全相同），那么他们都彼此认为这次见面是一次「完美的见面」。但是小明和小红并不总是能享受到这种服务，比如两者行走经过的站台没有任何交集，那么即使他们都被加入了某些保安的特别关注名单，也不会被火车站广播，从而导致他们不能见面，这样的话即使最终见面了也非常不愉快，因为这是一次不完美的见面。

当然火车站的人流量并不总是特别大，有时候小明和小红在同一个出口相遇了也有可能一眼认出对方，这样就不需要情侣见面帮助服务了，还有些时候小明和小红在同一个出口相遇，虽然没有一下子认出对方，但走着走着，有一方会突然想起刚才好像错过了什么，于是会瞬间到传呼台，呼叫另一半，另一半也会立刻停下步伐（停在某个出口），在原地等待他/她的到来。像这样的话他们其实就不会被火车站所广播，他们会觉得对方有足够的默契，因此会非常开心，再加上如果这次还能是一次「完美的见面」（即能够愉快地相互分享刚才路上的见闻），那么他们会认为这是一次「超级完美的见面」。

现在小明想知道他总共有多少次「超级完美的见面」的机会，由于这个数字可能很大，你需要输出这个数字对 $10^9+7$ 取模的结果。

---

一句话题意：

给定 $n$ 个数 $a_1,a_2,\ldots ,a_n$，这里定义一个二元组为 $(c,d)$ 并且满足 $c\le d$，两个二元组 $(c,d),(e,f)$ 相同当且仅当 $c=e,d=f$。

一个二元组对被表示为 $((c,d),(e,f))$，即一个二元组对包含了两个二元组，你需要求出有多少个不同的二元组对 $((c,d),(e,f))$ 满足如下条件：

• $c<e\le d$，$d<f$。
• $\forall a_u(e\le u\le d)$，满足 $a_u$ 只在 $a_{c\sim f}$ 中出现了一次。

两个二元组对不相同当且仅当其中一个二元组对包含的二元组不在另一个二元组对中。

Input

第一行输入一个整数 $n\ (1\le n\le 10^5)$ 代表火车站的小型出口的数目。

第二行输入 $n$ 个整数 $a_i\ (0\le a_i\le 10^9)$ 依次代表从北到南的小型出口编号。

Output

输出一个整数，代表小明的「超级完美的见面」的总次数对 $10^9+7$ 取模的结果。

Samples

5
1 2 1 2 3

4

6
1 1 2 1 2 1

4

Note

对于样例一，存在如下四种满足条件的不同二元组对：

• $((1,2),(2,3))$
• $((2,3),(3,4))$
• $((2,3),(3,5))$
• $((3,4),(4,5))$

Resources

2021 UESTC ICPC Training for Data Structures