## Algorithm

Problem Name: Data Structures - Array and Queries

In this HackerRank in Data Structures - Array and Queries solutions,

Given an array, you are asked to perform a number of queries and divide the array into what are called, beautiful subsequences.

The array A has length n. A function f(A) is defined to be a minimal possible x, such that it's possible to divide array A into x beautiful subsequences. Note that each element of an array should belong to exactly one subsequence, and subsequence does not necessarily need to be consecutive. A subsequence S with length len is called beautiful if and only if:

• len = 1 or
• Let S' be a sorted version of S. It must hold that S'i = S'i + 1 - 1 for every i epsolunot[1,len - 1].

For instance, if A = [1,2,3,4,5],f(A) would be 2. Because, you can divide A into 2 beautiful subsequences either like [1,2,3] and [4,3,5] or like [1,2,3,4,5] and .

You have to answer q queries. Each query is of the type:

• id val: you need to change a value of Aid to val , i.e. Aid = val. Here id is 1 - indexed

After each query, for the value of f(A) , lets denote that value as ans, where i indicates the ith query.

Input Format

The first line contains a single integer n, representing the length of array A.

The next line contains the array A given as space-separated integers.

The next line contains a single integer q, representing the number of queries.
Each of the q lines contain two integers id and val which is described above.

Constraints

• 1 <= n,q <= 3 * 105
• 1 <= Ai <= 109
• 1 <= id <= n
• 1 <= val <= 109

Output Format

Print the required answer in one line.

Sample Input 0

5
2 2 1 1 1
2
3 2
5 5


Sample Output 0

11


## Code Examples

### #1 Code Example with C++ Programming

Code - C++ Programming


#include <bits/stdc++.h>
using namespace std;
long int mod=1000000007 ;
int main(){
int n;
cin >> n;
multiset set1;
int arr[n];
for(int i = 0; i < n; i++){
cin>>arr[i];
set1.insert(arr[i]);
}
multiset set2=set1;
int count=0;
while(set2.size()){
count++;
int cur=*(set2.begin());
set2.erase(set2.find(cur));
while((set2.find(cur+1))!=set2.end()){
cur++;
set2.erase(set2.find(cur));
}
}
long long int q;
cin>>q;
long long int ans=0;
for(long long int i = 0; i < q; i++){
int id,val;
cin >> id >> val;
id--;
int curr=set1.count(arr[id]);
int prev=set1.count(arr[id]-1);
int next=set1.count(arr[id]+1);
//cout << '\t'<max(prev,next))
count--;
else if(curr<=min(prev,next))
count++;
set1.erase(set1.find(arr[id]));
arr[id]=val;
curr=set1.count(arr[id]);
prev=set1.count(arr[id]-1);
next=set1.count(arr[id]+1);
//cout << '\t' << curr<< '\t' << prev << '\t'<< next << '\n';
if(prev == 0 && next == 0)
count++;
else if((curr+1)>max(prev,next))
count++;
else if((curr+1)<=min(prev,next))
count--;
set1.insert(val);
ans=(ans+((i+1)*(count))%mod)%mod;
}
cout << ans;
return 0;
}


Copy The Code &

### #2 Code Example with Python Programming

Code - Python Programming


#!/bin/python3

import math
import os
import random
import re
import sys

#
# Complete the 'arrayAndQueries' function below.
#
# The function is expected to return an INTEGER.
# The function accepts following parameters:
#  1. INTEGER_ARRAY A
#  2. 2D_INTEGER_ARRAY queries
#

def arrayAndQueries(A, queries):
def f(vo):
count = 0
v = vo.copy()
while v:
nextn = min(v) + 1
v.remove(nextn - 1)
while nextn in v:
v.remove(nextn)
nextn += 1
count += 1
return count

result = 0
for i in range(len(queries)):
A[queries[i]-1] = queries[i]
result += (i+1)*f(A)

return result

if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')

n = int(input().strip())

A = list(map(int, input().rstrip().split()))

q = int(input().strip())

queries = []

for _ in range(q):
queries.append(list(map(int, input().rstrip().split())))

result = arrayAndQueries(A, queries)

fptr.write(str(result) + '\n')

fptr.close()


Copy The Code &