MISSING - Missing Number

no tags 

Given two numbers N and K, consider the following sequence of N integers:

K, K + 1, K + 2 ... K + N - 1

You will be given N - 1 of those integers in any order, and you will have to find the missing number in the sequence.

Input

The first line of input contains two numbers separated by one space, N and K, where 1 < N <= 107 and 1 <= K <= 231-1.

The second line contains N – 1 integers from the sequence specified above, with one space between each integer. The N – 1 numbers are arranged in no particular order. One of the numbers in the sequence is missing.

Output

Output a single line containing the missing number in the sequence.

Example

Input 1:
5 4
5 4 7 6

Output 1:
8
Input 2:
3 2
4 2

Output 2:
3

hide comments
emilll: 2014-01-26 06:29:47

my english not so good, don't understand this thing, can anyone explain in simple way?

Rocker3011: 2013-03-06 21:56:00

disagree with tutorial, the problem has a nice logic behind it. Move to classical

:D: 2013-03-06 09:33:02

First don't move this to classical because it's very basic.

I'm not sure how to change memory, but right now you would fail every single AC submission. I also don't see how you could do this problem using O(1) memory. On top of all that memory counting is pretty wonky on SPOJ (at least for now). It sometimes doesn't count dynamically allocated memory for example.

power: 2013-03-06 06:13:14

definitely, should be in tutorial!!!

ANKIT BATHLA: 2013-03-05 22:14:54

easy one!!!!!!

Angel Paredes: 2013-03-05 16:50:11

Hello SPOJ, I'm the problem setter for this problem. Does anybody know how to limit the RAM memory used? I'd like to restrict it to 1 MB.

Last edit: 2013-03-05 16:50:22
[Lakshman]: 2013-03-05 16:39:54

@Ehor Nechiporenko Thanks a lot for pointing out my mistake...

Ehor Nechiporenko: 2013-03-05 16:39:54

@Lakshman, it's easy. You have array of int a[]. But numbers are out of int ranges.

[Lakshman]: 2013-03-05 16:39:54

GOT AC :)

Last edit: 2013-03-05 13:08:33

Added by:Angel Paredes
Date:2013-03-05
Time limit:0.5s-1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Frank Arteaga