We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • Hackerrank Home
  • Practice
  • Certification
  • Compete
  • Career Fair
  • Hiring developers?
  1. Practice
  2. Data Structures
  3. Advanced
  4. Array and Queries

Array and Queries

Problem
Submissions
Leaderboard
Discussions

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

The array has length . A function is defined to be a minimal possible , such that it's possible to divide array into 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 with length is called beautiful if and only if:

  • or
  • Let be a sorted version of . It must hold that for every

For instance, if , would be . Because, you can divide into beautiful subsequences either like and or like and .

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

  • : you need to change a value of to , i.e. . Here is .

After each query, for the value of , lets denote that value as , where indicates the query.

You need to find modulo .

Input Format

The first line contains a single integer , representing the length of array .
The next line contains the array given as space-separated integers.
The next line contains a single integer , representing the number of queries.
Each of the lines contain two integers and , which is described above.

Constraints

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

Explanation 0

The initial array is

  • After query the array becomes this can be divided into subsequences as , and .
  • After query the array becomes this can be divided into subsequences as , , and .

image

Hence, calculating we get

Sample Input 1

2
3 3
3
2 4
1 5
2 2

Sample Output 1

9

Explanation 1

The initial array is

  • After query the array becomes this can be divided into subsequence as .
  • After query the array becomes this can be divided into subsequence as .
  • After query the array becomes this can be divided into subsequences as and .

Hence, calculating we get

Author

Birjik

Difficulty

Hard

Max Score

60

Submitted By

168

Need Help?


View discussions
View top submissions

rate this challenge

MORE DETAILS

Download problem statement
Download sample test cases
Suggest Edits
  • Contest Calendar
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature