Sonya and Robots CodeForces - 1004C(사고)

C. Sonya and Robots
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
Since Sonya is interested in robotics too, she decided to construct robots that will read and recognize numbers.
Sonya has drawn nn numbers in a row, aiai is located in the ii-th position. She also has put a robot at each end of the row (to the left of the first number and to the right of the last number). Sonya will give a number to each robot (they can be either same or different) and run them. When a robot is running, it is moving toward to another robot, reading numbers in the row. When a robot is reading a number that is equal to the number that was given to that robot, it will turn off and stay in the same position.
Sonya does not want robots to break, so she will give such numbers that robots will stop before they meet. That is, the girl wants them to stop at different positions so that the first robot is to the left of the second one.
For example, if the numbers [1,5,4,1,3][1,5,4,1,3] are written, and Sonya gives the number 11 to the first robot and the number 44 to the second one, the first robot will stop in the 11-st position while the second one in the 33-rd position. In that case, robots will not meet each other. As a result, robots will not be broken. But if Sonya gives the number 44 to the first robot and the number 55 to the second one, they will meet since the first robot will stop in the 33-rd position while the second one is in the 22-nd position.
Sonya understands that it does not make sense to give a number that is not written in the row because a robot will not find this number and will meet the other robot.
Sonya is now interested in finding the number of different pairs that she can give to robots so that they will not meet. In other words, she wants to know the number of pairs (pp, qq), where she will give pp to the first robot and qq to the second one. Pairs (pipi, qiqi) and (pjpj, qjqj) are different if pi≠pjpi≠pj or qi≠qjqi≠qj.
Unfortunately, Sonya is busy fixing robots that broke after a failed launch. That is why she is asking you to find the number of pairs that she can give to robots so that they will not meet.
Input
The first line contains a single integer nn (1≤n≤1051≤n≤105) — the number of numbers in a row.
The second line contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤1051≤ai≤105) — the numbers in a row.
Output
Print one number — the number of possible pairs that Sonya can give to robots so that they will not meet.
Examples
input
Copy

5
1 5 4 1 3

output
Copy

9

input
Copy

7
1 2 1 1 1 3 2

output
Copy

7

Note
In the first example, Sonya can give pairs (11, 11), (11, 33), (11, 44), (11, 55), (44, 11), (44, 33), (55, 11), (55, 33), and (55, 44).
In the second example, Sonya can give pairs (11, 11), (11, 22), (11, 33), (22, 11), (22, 22), (22, 33), and (33, 22)
제목: n으로 긴 수열 (숫자는 중복될 수 있음) 을 제시하고 i호의 위치를 표시하는 숫자는ai이다.현재 수열의 가장 왼쪽과 가장 오른쪽에 번호 로봇이 하나 있는데, 가장 왼쪽의 로봇은 오른쪽으로 이동하고, 가장 오른쪽의 로봇은 왼쪽으로 이동하며, 한 위치로 이동할 때마다 로봇은 이 위치의 숫자를 보고한다.현재 모든 로봇은 하나의 번호를 가지고 있는데 로봇이 제시한 숫자가 이 번호와 같으면 로봇은 이동을 멈추게 된다.이 두 로봇의 번호가 몇 가지인지 물어보면 이 두 로봇이 충돌하지 않도록 할 수 있다.
사고방식: 로봇이 충돌하지 않도록 하려면 로봇이 만나기 전에 이동을 멈춰야 한다.우리는 1번 위치부터 검사를 시작하여 1번 위치 뒤에 몇 개의 다른 숫자가 있는지 판단한 다음에 2번 위치부터 검사를 시작하여 2번 위치 뒤에 몇 개의 다른 숫자가 있는지 판단한다. 이에 따라 모든 결과를 합치면 된다(주의, i번 위치에서 뒤에 있는 숫자를 검사할 때 이 위치의 수와 출현한 적이 있는지 판독해야 한다).직접 폭력 검사를 한다면 틀림없이 tle가 될 것이다. 따라서, 우리는 각 위치 뒤에 있는 서로 다른 숫자의 개수를 미리 처리한 다음에 누적된다.

#include "iostream"
#include "cstring"
using namespace std;
const int Max=1e5+10;
int a[Max],vis[Max],sum[Max];
int main()
{
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=n;i>=1;i--){//   
        if(vis[a[i]]) sum[i]=sum[i+1];//  i           
        else sum[i]=sum[i+1]+1,vis[a[i]]=1;
    }
    memset(vis,0, sizeof(vis));
    long long ans=0;
    for(int i=1;i