QBALL - Balls and Queries

no tags 

Xima has N balls arranged together in a line, the i-th (1 ≤ i ≤ N) ball has a value of Ai.

Tzaph asks Q queries to Xima. There are two types of queries:

  • 1 i k: The value of the i-th ball is changed into k. In other words, Ai = k. Take note that Ai and k could have a same value. In this case, Xima shouldn't do anything.
  • 2 i: Tzaph removes the i-th ball out from the line. Print the number of pairs (x, y) such that the x-th and the y-th ball is in the line,  x < y, and Ax = Ay. After this query, Tzaph returns the i-th ball back to the line in its original position.

However, Tzaph asks too many queries and Xima has too many balls. Xima asks you to help him answer all of Tzaph's queries. Help him out!

Input

The first line contains two integers N and Q.

The second line consists of N integers, where the i-th integer represents Ai.

The next Q lines represents the queries with format explained in the description.

Output

For every second type of query, print the answer required.

Constraints

1 ≤ N, Q, Ai, k ≤ 105

Examples

Input 1:
5 5
1 2 3 4 5
1 2 3
1 5 4
2 1
1 2 4
2 4

Output 1:
2
1
Input 2:
1 3
1
2 1
1 1 3
2 1

Output 2:
0
0

hide comments
Vipul Srivastava: 2020-05-21 18:51:11

@maximath_1 can you please check my submission once and let me know if I am totally wrong or I am missing some tests? I am kind of stuck here...
Submission Id: 26016984

Reply from author: Your idea is not wrong but there is a bug in your code. Try to debug your code!

@author thanks a lot for your reply, I was over complicating the code, I got an AC now, btw nice question :)

Last edit: 2020-05-23 13:59:35
nadstratosfer: 2020-05-21 16:06:10

Statement implies ordering of the values that is not conveyed intuitively by story about balls in a bag, please consider rephrasing it. Also get rid of formatting that makes samples invisible in dark mode, see the screenshot at KONSTRAKSCHION.

Reply from Author: Fixed, thank you for the input! I am not aware that the formatting made the samples invisible.

[NG]: Thanks for the corrections. Good problem, enjoyed.

Last edit: 2020-05-21 23:14:15

Added by:Maximilliano
Date:2020-05-21
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Own problem, a buffed version of https://atcoder.jp/contests/abc159/tasks/abc159_d