An encoder for encoding, for the purpose of compression, a sequence of integer values, hereinafter referred to as "input sequence", which is obtained by converting a sound signal in the time domain into an MDCT coefficient sequence in the frequency domain and by converting coefficients of the MDCT coefficient sequence into non-negative integer values, the encoder comprising: an integer selector that, for each set of S+1 integer values, hereinafter referred to as "input integer values", in the input sequence, where S is an integer of two or more, selects 2 integer values as a first integer value that is an integer value having the smallest sample number from the S+1 input integer values and a second integer value that is an integer value having the largest value from S input integer values having larger sample numbers among the S+1 input integer values, and obtains selection information that specifies which of the S input integer values having larger sample numbers among the S+1 input integer value the second integer value is, where a sample number is a cardinal position of the coefficient within the subsequence of S+1 MDCT coefficients along the frequency axis; an integer integrator that obtains one integer value, hereinafter referred to as "converted integer value", by reversibly converting each set of the first integer value, the second integer value and an integer value corresponding to the selection information and obtains a converted integer sequence which is a sequence of the obtained converted integer values; and an integer encoder that determines the number of bits to be assigned to each converted integer value included in the converted integer sequence, obtains a code in which a binary number which represents the converted integer value included in the converted integer sequence is fitted into the determined number of bits, and outputs a code group of the obtained codes. an integer selector that, for each set of S+1 integer values, hereinafter referred to as "input integer values", in the input sequence, where S is an integer of two or more, selects 2 integer values as a first integer value that is an integer value having the smallest sample number from the S+1 input integer values and a second integer value that is an integer value having the largest value from S input integer values having larger sample numbers among the S+1 input integer values, and obtains selection information that specifies which of the S input integer values having larger sample numbers among the S+1 input integer value the second integer value is, where a sample number is a cardinal position of the coefficient within the subsequence of S+1 MDCT coefficients along the frequency axis; an integer integrator that obtains one integer value, hereinafter referred to as "converted integer value", by reversibly converting each set of the first integer value, the second integer value and an integer value corresponding to the selection information and obtains a converted integer sequence which is a sequence of the obtained converted integer values; and an integer encoder that determines the number of bits to be assigned to each converted integer value included in the converted integer sequence, obtains a code in which a binary number which represents the converted integer value included in the converted integer sequence is fitted into the determined number of bits, and outputs a code group of the obtained codes.